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

×

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

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);
        }
    }
}

asked 12 Aug '18, 10:59

chandubaba's gravatar image

2★chandubaba ♢
13311
accept rate: 0%

edited 12 Aug '18, 11:37

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

(12 Aug '18, 14:41) beardaspirant3★

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

link

answered 12 Aug '18, 15:40

vishesh345's gravatar image

3★vishesh345
444
accept rate: 0%

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

(12 Aug '18, 21:01) beardaspirant3★

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_14076★

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

(13 Aug '18, 23:59) beardaspirant3★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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