You are not logged in. Please login at www.codechef.com to post your questions!

×

# 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)
s[a/g, b/g].add((a/h, b/h, c/h))
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:

This question is marked "community wiki".

asked 12 Dec '15, 23:19 1.7k586142
accept rate: 11% 19.8k350498541

 3 Author's Solution is giving wrong answer in all cases please fix your code @author :) Good editorial. Thanks answered 06 Jan '16, 20:29 820●2●12 accept rate: 3%
 2 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 1.1k●1●8 accept rate: 10%
 2 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 5★apptica 949●2●10 accept rate: 17%
 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 answered 15 Dec '15, 14:53 781●8 accept rate: 7%
 0 @kevinsogo I can't access the setter and tester solutions. Its saying access denied answered 14 Dec '15, 15:53 499●1●8 accept rate: 15%
 0 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. answered 14 Dec '15, 16:21 4★konfused 21●1 accept rate: 0% Got it!! Precision set to 10^-16 Here is correct solution - https://www.codechef.com/viewsolution/8974725 (18 Dec '15, 12:43) konfused4★
 0 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 5★raj61 1 accept rate: 0% 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) aragar4★
 0 Java solution by storing the slope in Map https://www.codechef.com/viewsolution/8905572 answered 15 Dec '15, 12:14 2★dp13 11 accept rate: 0%
 0 I also tried something like sorting by slope, but without converting to float. Here is my solution. Could you help me identify the mistake? answered 15 Dec '15, 14:11 4★aragar 99●5 accept rate: 7%
 0 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 3★aj619 1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/8965354 can anyone plz tell me where my code fails answered 16 Dec '15, 15:28 1●1 accept rate: 0% 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. (17 Dec '15, 14:08) aragar4★ 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) aragar4★
 0 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 4★aragar 99●5 accept rate: 7%
 0 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 1 accept rate: 0%
 0 Setter's and Tester's solution showing WA in all the test cases.... :| answered 29 Dec '15, 16:34 1 accept rate: 0%
 0 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 4★akchamp 124●1●9 accept rate: 20%
 0 What's the bug in setter's solution? :( answered 03 Mar '16, 00:38 3★esemzv 21●2 accept rate: 0%
 0 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 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,875
×1,191
×801
×321
×174
×163
×26
×6

question asked: 12 Dec '15, 23:19

question was seen: 5,038 times

last updated: 16 hours ago