 # PLANEDIV - Editorial

Author: Maksym Bevza
Tester: Sergey Kulik
Editorialist: Kevin Atienza

### 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:

• First, we must be able to represent the slope exactly, and not just a floating point number, otherwise you risk getting wrong answer due to bad rounding. (Remember that many numbers cannot be represented exactly in floating point.)
• Second, we must be able to detect whether two lines coincide, because we should only count coinciding lines once.

We’ll deal with these problems one by one.

# Representing the slope

First, 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 error-free 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 1

Well, 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 2

There’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_2-x_1, y_2-y_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_2-x_1) + B(y_2-y_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 lines

Next, 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:

4x + 6y + 1 = 0
8x + 12y + 2 = 0
44x + 66y + 22 = 0
-44x - 66y - 22 = 0

However, these lines do not coincide with the line 4x + 6y + 2 = 0 or 4x + 6y - 1 = 0.

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:

• C > 0
• C = 0 and B > 0
• C = 0, B = 0 and A > 0

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:

• y > 0
• y = 0 and x > 0

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!

# Solution

Armed 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:

from fractions import gcd
from collections import defaultdict
s = defaultdict(set)
for i in xrange(input()):
a, b, c = map(int, raw_input().strip().split())
g = gcd(a, b)
h = gcd(g, c)
print max(map(len, s.values()))


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:

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

2 Likes

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.

2 Likes

@kevinsogo I can’t access the setter and tester solutions. Its saying access denied

I tried this problem using calculating slope & intercept - using y = mx+c.
It still gives 1 WA in both subtasks.
https://www.codechef.com/viewsolution/8955195
Is this because of precision or is there any other issue ?
Providing testcase will be really helpful.

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

Java solution by storing the slope in Map
https://www.codechef.com/viewsolution/8905572

I also tried something like sorting by slope, but without converting to float. Here is my solution. Could you help me identify the mistake?

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.

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

2 Likes

i just ran the authors solution in prctice link of the problem… in c++14…
giving wrong answer!!! https://www.codechef.com/viewsolution/8965354

can anyone plz tell me where my code fails

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 :\

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 slow-but-correct solution to test it? I can send you mine, if you would like.

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 Just take in mind that I write for stuff then the given output, just check the generator first.

Got it!!

Precision set to 10^-16

Here is correct solution -

https://www.codechef.com/viewsolution/8974725

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

Setter’s and Tester’s solution showing WA in all the test cases… My solution gives RE (SIGSEGV) for 2 test cases please sm1 cud explain.
thanks in advance https://www.codechef.com/viewsolution/9105598

//