QM10P5B editorial

PROBLEM LINK:

Practice

Contest

Author: Chandan Boruah

Tester: Taranpreet Singh

Editorialist: TaranPreet Singh

DIFFICULTY:

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. :slight_smile:

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()
	{
		int t=int.Parse(Console.ReadLine());
		while((t--)>0)
		{
			int n=int.Parse(Console.ReadLine());
			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++)
			{
				string[]ss=Console.ReadLine().Split();
				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))
				{
					slopes.Add(slope);
				}
			}
			Console.WriteLine(slopes.Count);
		}
	}
}

@beardaspirant handle cases for 0 slope and infinity slope separately.

1 Like

can someone point the mistake in CodeChef: Practical coding for everyone

why?? wouldn’t infinity be handled automatically by Java Double? and 0 slope is anyhow 0.

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.

@taran_1407 this would be handled by Java. Double has infinity and will never get div by 0 error.