This is a walkthrough on how I solved the competitive coding problem PLANEDIV which appeared on CodeChef’s December Challenge 2015 using Java. I will include the code and also the explanation. You can find the problem at https://www.codechef.com/problems/PLANEDIV
Problem Statement:
First we start by looking through the problem statement.
Chef is working with lines on a 2-D plane.
He knows that every line on a plane can be clearly defined by three coefficients A, B and C: any point (x, y) lies on the line if and only if A * x + B * y + C = 0.
Let’s call a set of lines to be perfect if there does not exist a point that belongs to two or more distinct lines of the set.
He has a set of lines on a plane and he wants to find out the size of the largest perfect subset of this set.
Simplified:
So the problem statement defines a perfect set as a set of lines in which no point belongs to two or more distinct lines of that set.For a point to not belong to two distinct lines, the two lines must not intersect. That is, they must be parallel.
In it’s most basic form, the problem asks us to find the set containing the largest number of DISTINCT PARALLEL lines.
Mathematical Explanation:
To do that we invoke our knowledge of basic 2D geometry. Two lines are parallel if they have the same slope. And they are distinct if they have different intercepts. So, for two lines to be distinct and parallel, they have to have the same slope but different intercepts.
This is the basic mathematical concept required to solve this problem.
Java Explanation:
There are N lines in the input and each line has 3 characteristics A (X – coefficient), B (Y – coefficient), C (Intercept). We will store them all in a 2 Dimensional array of double data type having N x 3 elements.
We use a string tokenizer to parse the data into our 2D array. While parsing the input, lets also calculate the slope. Straight off the bat, we see a problem. For lines parallel to the Y – axis, the slope is infinity. We will store this as -0.0. For such lines the Y – Coefficient is 0 we will evaluate the slope of such lines to -0.0 (Infinty) separately.
Java allows us to distinguish between 0.0 and -0.0. Its just another odd quirk of the double data type in java and we will take advantage of it.
Java does allow you to store infinity as “Infinity” in the double class, but I’ll be ignoring that as -0.0 will be
easier to deal with, in my opinion.
Another problem is for lines parallel to the X – Axis, they have Infinite Intercept. We will use their Y -Intercept instead of their X – Intercept to distinguish between lines parallel to the X – Axis.
Now all we have to do is get the slopes of eaach line, relate it to itss intercept, and see how many lines have the same slope but different intercept. The largest of those numbers gives the answer.
The slope is given by
if(Coefficient of Y != 0)
slope = - Coefficient of X / Coefficient of Y = -A/B
else
slope = -0.0
and the intercept
if(Coefficient of Y != 0)
slope = - Intercept / Coefficient of Y = -C/B
else
slope = - Intercept / Coefficient of X = -C/B
Once we’ve calculated the slopes and intercept, we simply store them pair wise in a data structure. 2D arrays can be used but a neater implimentation would be to use the Point class in Java. It takes two parameters X and Y. In our case, X would be the slope and Y would be the intercept.
Then we count the number of lines with same slope but different intercept. To make this easier we use the Comparable interface to sort them by slope and then by intercept.
List points = new ArrayList();
for (int m = 0; m < N; m++) {
points.add(new Point.Double(slopes[m], intercepts[m]));
}
Collections.sort(points, new Comparator() {
public int compare(Point.Double x1, Point.Double x2) {
int result = Double.compare(x1.getX(), x2.getX());
if (result == 0) {
result = Double.compare(x1.getY(), x2.getY());
}
return result;
}
});
The last thing to do is to count the number of lines with same slope and different intercept. The largest of these will be the answer.
The Final Solution:
Putting it all togethter, we have the solution.
Java Solution Code : PLANEDIV – CodeChef Problem
It passes all test cases in 0.25 seconds, giving us the full 100 points.
The code should be self explanatory after reading the about tutorial but if you do have any questions, feel free to post them as a comment.
-Tutorial by Karthikeyan M
