×

# QM10P5B editorial

Author: Chandan Boruah
Tester: Taranpreet Singh
Editorialist: TaranPreet Singh

Easy

# PREREQUISITES:

Slope of a line, Observation.

# PROBLEM:

Given $N$ lines represented by two points, we need to find maximum number of lines which can pass through a single point, without superimposing any other line. we can move any line but not rotate it.

# QUICK EXPLANATION

• Represent lines as pair $(m, c)$ where line can be given as $y = mx+c$, called line slope form. We can now see that we can change the $c$ for any line, but cannot modify $m$.
• Lines with Same value of slope ($m$) are parallel to each other, given ($c_{1} \neq c_{2}$).
• No two parallel lines can pass through same point without superimposing each other.
• Our problem reduces to finding different values of slopes from the given set of lines.

# EXPLANATION

The quick Explanation says it all. :-)

We can calculate slope of a line as $(y_2 - y_1)/(x_2-x_1)$, add them to a set and count the number of distinct values of slope in set.

BUT BUT, what about REs we were getting in contest??

This was because of some lines having $x_1 = x_2$, test case specially added by devil tester :D, which caused arithmetic Division by zero error.

We need to handle vertical (and probably horizontal too, if we wish) lines separately. Maybe having two boolean values horizontal and vertical would do fine. Each boolean value indicate whether input set contains a vertical (or horizontal) line.

If true, would each of them contribute 1 to final answer.

Complexity:
Time Complexity is $O(N)$.

# AUTHOR'S SOLUTIONS:

using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
while((t--)>0)
{
int[]x1=new int[n];
int[]y1=new int[n];
int[]x2=new int[n];
int[]y2=new int[n];
for(int i=0;i<n;i++)
{
x1[i]=int.Parse(ss[0]);
y1[i]=int.Parse(ss[1]);
x2[i]=int.Parse(ss[2]);
y2[i]=int.Parse(ss[3]);
}
SortedSet<double>slopes=new SortedSet<double>();
for(int i=0;i<n;i++)
{
double slope=0;
if(y1[i]==y2[i])
{
slope=int.MaxValue;
}
else
slope=(x1[i]-x2[i])*1.0/(y1[i]-y2[i]);
if(!slopes.Contains(slope))
{
}
}
Console.WriteLine(slopes.Count);
}
}
}


13311
accept rate: 0%

can someone point the mistake in https://www.codechef.com/viewsolution/19680526

(12 Aug '18, 14:41)

 1 @beardaspirant handle cases for 0 slope and infinity slope separately. answered 12 Aug '18, 15:40 44●4 accept rate: 0% why?? wouldn't infinity be handled automatically by Java Double? and 0 slope is anyhow 0. (12 Aug '18, 21:01) Suppose you have line given by points (1, 1) and (1, 3). Now, by using above formula for slope, we would get divide by zero error. We can handle this by checking if x1==x2, and handle this case separately. Slope 0 need not to be handled separately, but can be done if you wish to. (13 Aug '18, 01:09) @taran_1407 this would be handled by Java. Double has infinity and will never get div by 0 error. (13 Aug '18, 23:59)
 toggle preview community wiki:
Preview

By Email:

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,852
×303
×170

question asked: 12 Aug '18, 10:59

question was seen: 139 times

last updated: 13 Aug '18, 23:59