TWOROADS - Editorial
# Problem Link:
[Practice](http://www.codechef.com/problems/TWOROADS)<br>
[Contest](http://www.codechef.com/SEPT13/problems/TWOROADS)
# Difficulty:
Hard
# Pre-requisites:
High School Geometry
# Problem:
Given a set **S** of **N** points in plane, you have to draw two lines such that sum of squares of distance of each point from nearest line is smallest.
# Explanation:
The first thing one realizes about this problem is that the business of taking minimum of the distances is causing all the trouble. If we had to draw a single line to optimize sum of squares of its distance from all points, it would be a piece of cake. High school calculus can be used to find the optimum equation of the line. Here is a brief sketch:
Let the equation of optimum line be **y +mx +c = 0**. The square of distance of a point **(x0,y0)** from this line is **(y0 + mx0 + c)<sup>2</sup>/(1 + m<sup>2</sup>)**. Therefore, sum of squares of distance of all points is
> (Y2 + m<sup>2</sup>X2 + c<sup>2</sup> * N + 2 * m * XY + 2 * Y * c + 2 * m * X * c) / (1 + m<sup>2</sup>)
> where Y2 = sum<sub>i</sub> y<sub>i</sub><sup>2</sup>, X2 = sum<sub>i</sub> x<sub>i</sub><sup>2</sup>, XY = sum<sub>i</sub> y<sub>i</sub>x<sub>i</sub>, X = sum<sub>i</sub> x<sub>i</sub>, Y = sum<sub>i</sub> y<sub>i</sub>, N = sum<sub>i</sub> 1
We need to find optimum **m** and **c**. To do this, first differentiate with respect to **c** to get **c** as a (linear)function of **m**, plug it in the above, and differentiate with respect to **m** to get optimum value. Refer to solutions at the end for more precise details. Assuming that the one line case can be solved in constant time, given **X, Y, XY, N, X2, Y2**, we can now proceed.
Now imagine the optimal pair of lines. Let the lines be named **A** and **B**. Every point in our set **S** is closer to exactly one of **A** and **B**. Let **S<sub>A</sub>** be the set of points in our **S** closer to **A** than **B**. Similarly define **S<sub>B</sub>**. Note that **S<sub>B</sub> = S - S<sub>A</sub>**.
Now suppose, by some magic, we managed to find the set **S<sub>A</sub>**. Then we would again be done. This is because line **A** is the optimal line for the set **S<sub>A</sub>**, and line **B** is the optimal line for remaining points.
Cool ! So, we now have a **O(N * 2<sup>N</sup>)** solution, which basically iterates over all subsets **S<sub>A</sub>** of **S**, and reports the solution.
Obviously, the next step is to note that sets **S<sub>A</sub>** and **S<sub>B</sub>** cannot be arbitrary. If we are given a pair of lines **A** and **B**, then **S<sub>A</sub>** consists of exactly those points in **S** which do not lie in the colored region. Similarly, **S<sub>B</sub>** consists of those points which lie in the colored region. Justification is very straightforward and left to the reader. The colored region can be identified by a pair of perpendicular lines. For any two perpendicular lines **L, M**, let **R<sub>L,M</sub>** denote the the first and third quadrant of the co-ordinate system defined by line **L, M**. Formally, **R<sub>L,M</sub> = {points P | tan ∠ PXL ≥ 0}**, **X** being intersection point of **L** and **M**.
<img src="http://i42.tinypic.com/2in53t.png" width="65%"/>
Due to discussion above, we know that the set **S<sub>A</sub>** cannot be arbitrary. The set **S<sub>A</sub>** has to be such that there exist two perpendicular lines **L** and **M**, so that **S<sub>A</sub> = S ∩ R<sub>L,M</sub>**.
In fact, we give a list **Z** of pairs of lines(i.e. **Z={(L<sub>1</sub>, M<sub>1</sub>), (L<sub>2</sub>,M<sub>2</sub>), ... (L<sub>M</sub>,M<sub>M</sub>)}**) such that, for any arbitrary pair of lines **(L, M)** we can obtain another pair of lines **(L', M')** which satisfies the following
* **S ∩ R<sub>L,M</sub> = S ∩ R<sub>L',M'</sub>**
* **(L', M') ∈ Z**
> In other words, the possible lines **L** and **M** can be infinite in number, but we can find a finite set of pairs of lines which still induce all possible partitions of the given set **S**. In fact we can show that the required number of pairs of lines is polynomial in **N**.
Here is how to obtain **L', M'** from any **L, M**.
<img src="http://i42.tinypic.com/m6hcp.png" width="65%"/>
* Translate **L**, parallel to itself towards left, right, until **L** _hits_ some point **P<sub>1</sub> ∈ S**. Stop translating when it is infinitesimally small distance away from **P<sub>1</sub>**.
<img src="http://i43.tinypic.com/2zdmv4h.png" width="65%"/>
* Now translate **M**, parallel to itself towards left, right, until it _hits_ some point **P<sub>2</sub> ∈ S**. Again stop translating when distance between line and point becomes infinitesimally small.
<img src="http://i42.tinypic.com/2n7i2qx.png" width="65%"/>
* Rotate both **L** and **M** clockwise so that i) **M** remains perpendicular to **L**, ii) One end point of **L** is fixed at **P<sub>1</sub>**, iii) One end point of **M** is fixed at **P<sub>2</sub>**. The intersection point of **L** and **M** moves in a circle with **P<sub>1</sub>P<sub>2</sub>** as diameter. Stop rotating when one of **L** or **M** _hits_ some point **P<sub>3</sub> ∈ S**. Again, stop rotating when it is infinitesimally small distance away from **P<sub>3</sub>**.
<img src="http://i42.tinypic.com/206fym9.png" width="65%"/>
Now it is clear that the new lines **L', M'** obtained by above process still induce same partition of **S** as **L, M** did. Moreover, **L', M'** are completely defined by
* Points **P<sub>1</sub>, P<sub>2</sub>, P<sub>3</sub>**.
* One bits indicating whether **P<sub>3</sub>** was _hit_ from above or below. It doesn't matter whether **L'** actually hit **P<sub>3</sub>** or **M'** because they are interchangeable. For further discussion, always assume that **L'** had hit **P<sub>3</sub>**.
The set **Z** of all possible final pairs **(L', M')** obtained after translation/rotation has size **2n<sup>3</sup>**, and can be easily enumerated. We can solve the problem in **O(n^3)** overall time as well, because the partitions imposed by these lines can be interconverted by adding/removing single points, and hence **(X, Y, XY, X2, Y2)** tuple can be re-calculated in constant time. See the solutions below for exact details.
# Setter's Solution:
Can be found [here](http://www.codechef.com/download/Solutions/SEPT13/Setter/TWOROADS.cpp)
# Tester's Solution:
Can be found [here](http://www.codechef.com/download/Solutions/SEPT13/Tester/sergey/TWOROADS.cpp)
# Editorialist's Solution:
Can be found [here](http://www.codechef.com/download/Solutions/SEPT13/Editorialist/TWOROADS.cpp)