PROBLEM LINK:Author: Maksym Bevza PREREQUISITES:Cartesian coordinates, parallel lines, sets, GCD, Euclidean algorithm, sorting PROBLEM:A set of lines is called perfect if there's no point that belongs to two distinct lines of the set. Given a set of $N$ lines, each determined by three coefficients $(A,B,C)$ (representing the line $Ax + By + C = 0$), what is the size of the largest perfect subset? QUICK EXPLANATION:The answer is simply the largest set of distinct lines that are all parallel to one another. To get the answer, group the lines according to slope, being careful to not count coinciding lines twice. (e.g. $x + y + 1 = 0$ coincides with $2x + 2y + 2 = 0$ so should only be counted once.) The answer is the size of the largest group. One way to group the lines is to add them to a set data structure. Another is to sort them according to slope, so that lines with the same slope are found consecutively. EXPLANATION:A set containing just one line is clearly perfect, so let's investigate perfect sets of size at least two. Let $a$ and $b$ be two lines in a perfect set. Since $a$ and $b$ must not intersect (and definitely must not coincide), then they must be parallel. In other words, they must have the same slope. Since this argument applies to any pair of lines in the perfect set, we can say that a perfect set is just a set of distinct lines all having a common slope. Our goal now is to find the largest perfect set. Naturally, we want to group the lines according to slope, and take the largest group as the answer. In fact, this is basically the algorithm to solve this problem! However, there are at least two problems that might come up when implementing this:
We'll deal with these problems one by one. Representing the slopeFirst, note that it's actually possible to get accepted while using floating point slopes (especially if the data isn't strong enough or the bounds of the problem prevents rounding errors from being a problem), but it's still important to know an errorfree way to represent slopes, in other words, a way that can be shown to always work. Also, representing a slope exactly has many applications even outside of this problem. So how do we represent the slope of a line exactly? Representation 1Well, one way to represent the slope exactly is to simply represent it as an exact fraction. For example, the slope of $Ax + By + C = 0$ is $A / B$. But we must be able to detect the same fractions! (For example, $1 / 2 = 2 / 4 = 3 / 6$.) One way to do it is to reduce the fraction to lowest terms, by dividing the numerator and denominator by the greatest common divisor (gcd). This works because rational numbers have a unique representation in lowest terms. We need to represent negative slopes as well! To make the "lowest term representation" unique, simply ensure that the denominator is always positive. Another problem that will arise is how to represent the slope of vertical lines. Their slope can't be represented by a rational number (because it's "infinite"). However, since there is a unique slope for vertical lines, we can simply use a unique object to represent the "vertical slope". (or just handle vertical lines separately) Representation 2There's actually a way to represent the slopes without needing any special handling for the vertical slope. Instead of representing the slope of the line as a rational number, we represent it as the vector pointing to the direction of the line. Remember that a vector is an ordered pair $\langle x, y \rangle$, which represents the direction pointing from $(0,0)$ towards $(x,y)$. (In a vector, the distance between these points are also important, but since we're only talking about the "direction" of the line, it doesn't matter for our purposes.) What is the direction vector of the line $Ax + By + C = 0$? Suppose $(x_1,y_1)$ and $(x_2,y_2)$ are points on this line. Then $\langle x_d, y_d \rangle = \langle x_2x_1, y_2y_1\rangle$ is one possible direction vector. But these points satisfy the equation of the line, so: $$Ax_1 + By_1 + C = 0$$ $$Ax_2 + By_2 + C = 0$$ Subtracting these two, we get: $$A(x_2x_1) + B(y_2y_1) = 0$$ or $$Ax_d + By_d = 0$$ But one solution to this equation is simply $x_d = B$ and $y_d = A$, thus $\langle B, A \rangle$ is one direction vector for the line $Ax + By + C = 0$! But in order to group our lines according to slope, we must again be able to detect vectors representing the same direction. Similarly to rational numbers, we must find some sort of "normal form" that we can reduce our direction vectors to. Note that we also consider opposing vectors as representing the same "direction", e.g. $\langle x, y \rangle$ and $\langle x, y \rangle$. One way to define such a normal form is the following. Let's say a vector $\langle x, y \rangle$ with integer coordinates is in normal form if and only if $x$ and $y$ are relatively prime and the polar angle of $(x,y)$ is less than 180 degrees. The reader is invited to prove that every direction vector has a unique normal form. Finally, to convert $\langle x, y \rangle$ to normal form, simply divide both coordinates by $\gcd(x,y)$, and then negate both if $y$ is negative, or $y = 0$ and $x$ is negative. Using vectors instead of slopes, we don't have to worry about "infinite" slopes any more! Detecting coinciding linesNext, what about detecting coinciding lines? Note that coinciding lines necessarily have the same slope, so we can simply look at lines with the same slope, and find among those the lines that overlap. Note that two lines overlap if and only if their equations are the same, up to a nonzero multiplicative constant. For example, the following lines all coincide with one another: In this case, we can simply try to reduce the equations into some sort of "normal form" (as in the previous section), in such a way that each equation of a line has a unique normal form. Here's one way: Let's say the equation $Ax + By + C = 0$ is in normal form if $A$, $B$ and $C$ are relatively prime, and one of the following conditions hold:
The idea behind this is actually just an extension of our "normal form" of direction vectors in the previous section, because $\langle x, y \rangle$ is in normal form if $x$ and $y$ are relatively prime and one of the following conditions is satisfied:
Thus, we can just reduce all our equations to their normal forms, and this way, two lines coincide if and only if their equations are equal! SolutionArmed with the above techniques, the solution is now easy. First, group the lines according to their slopes (or normal forms of their direction vectors). Then, for each group, compute the normal forms of their equations, and remove duplicates. Finally, the answer is simply the largest remaining group! The following is a Python implementation which solves a single test case:
Since Python's $\text{gcd}(a,b)$ is guaranteed to have the same sign as $b$, dividing by the gcd will already guarantee normality (as we've defined it). The time complexity of this algorithm is $O(N \log N)$ if one uses balanced tree sets. Alternatively, you can just sort them according to their normal forms, so parallel lines and coinciding lines are found consecutively. This runs in $O(N \log N)$ time also. Time Complexity:$O(N \log N)$ or expected $O(N)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Dec '15, 23:19

The problem is just to use a stable sort to sort according to the intercept after that with slope, removing duplicates and reporting the maximal set. The case where b=0, can be taken separately (slope infinity).. My simple solution using sort : https://www.codechef.com/viewsolution/8910675 answered 14 Dec '15, 15:35

Easy implementation using a set or map can be done to remove the duplicates and using y = m*x + c form of line. Insert pairs of slope and intercept into the set and then count the pairs with same slope. Duplicates will be auto removed. Std Map Solution Link answered 14 Dec '15, 15:44

let l1 : a1 x + b1 y + c1 = 0 l2 : a2 x + b2 y + c2 = 0 l1 and l2 are parallel if and only if a1/a2 = b1 /b2 != c1/c2 . I just sorted the lines by coefficients a,b,c so that identical and parallel lines come successively. if two lines are identical then a1 = a2 , b1 = b2 , c1 = c2 if two lines are parallel then a1 = a2 , b1 = b2 , c1! = c2 here's my java solution : https://www.codechef.com/viewsolution/8884085 answered 15 Dec '15, 14:53

@kevinsogo I can't access the setter and tester solutions. Its saying access denied answered 14 Dec '15, 15:53

I tried this problem using calculating slope & intercept  using y = mx+c. answered 14 Dec '15, 16:21
Got it!!
(18 Dec '15, 12:43)

I tried this problem with sorting line using comparison function...bt it gave WA in some test cases.. https://www.codechef.com/viewsolution/8945683 can u give me some test case where my code is giving error..link text answered 15 Dec '15, 10:50
I think I had the same problem like you at some point. So, if I understand correctly, your idea is to sort all the lines and check how many lines are next to each other and are parallel, but not equal? Ok, I can't give you a specific test currently, but imagine the following situation. After you sort the lines you have got a, b, c, d, e, which are all lines. And c == d, i.e. they are the same line. but b  c  d  e, i.e. b, c, d, and e are all parallel. Then the answer should be 3, right? But your code will stop at d, because it is the same line as c and it will produce the answer 2.
(15 Dec '15, 14:22)

Java solution by storing the slope in Map https://www.codechef.com/viewsolution/8905572 answered 15 Dec '15, 12:14

i just ran the authors solution in prctice link of the problem.. in c++14.. giving wrong answer!!!!!!! :p answered 16 Dec '15, 14:39

https://www.codechef.com/viewsolution/8965354 can anyone plz tell me where my code fails answered 16 Dec '15, 15:28
The only error I see is eventually of the error precision of the double. Did you try to write some test generator and a second slowbutcorrect solution to test it? I can send you mine, if you would like.
(17 Dec '15, 14:08)
yes please provide the link to your solution..
(17 Dec '15, 14:13)
You can find the file here. It contains the slow but correct solution, the generator and a bat to start it. It is a bit lame, but sorry :D Just take in mind that I write for stuff then the given output, just check the generator first.
(17 Dec '15, 15:05)

This is another example why I want the tests to be submitted after the contests. This is another task I can't solve because I can't find the error in my solution :\ I tried writing a test generator and a slow correct solution, but everything is ok for small tests :\ When I ask for help the setter won't help :\ answered 17 Dec '15, 14:06

I've used y=mx+c line equation and used cmp() function for sorting. Can anyone tell me the test cases where my solution fails. https://www.codechef.com/viewsolution/8929449 answered 20 Dec '15, 13:24

Setter's and Tester's solution showing WA in all the test cases.... : answered 29 Dec '15, 16:34

My solution gives RE (SIGSEGV) for 2 test cases please sm1 cud explain. thanks in advance :) https://www.codechef.com/viewsolution/9105598 answered 06 Jan '16, 14:52

Do we really need to consider the case of a vertical line? The statement states that "For a line with coefficients A, B and C either A or B is not zero". So when B can not be a zero then how it is possible to form a vertical line? answered 16 hours ago
