GreetingCard problem with Coordinates

Question

This is a practice problem on Kattis

I have exceeded the time limit for the 5th out of 11 test case. Can anyone inspire me what could be done to optimize the code?

Problem Description

Quido plans to send a New Year greeting to his friend Hugo. He has recently acquired access to an advanced high-precision plotter and he is planning to print the greeting card on the plotter.

Here’s how the plotter operates. In step one, the plotter plots an intricate pattern of n dots on the paper. In step two, the picture in the greeting emerges when the plotter connects by a straight segment each pair of dots that are exactly 2018 length units apart.

The plotter uses a special holographic ink, which has a limited supply. Quido wants to know the number of all plotted segments in the picture to be sure that there is enough ink to complete the job.

Input

The first line of input contains a positive integer n specifying the number of plotted points. The following n lines each contain a pair of space-separated integer coordinates indicating one plotted point. Each coordinate is non-negative and less than 2^31. There are at most 10^5 points, all of them are distinct.

In this problem, all coordinates and distances are expressed in plotter length units, the length of the unit in the x-direction and in the y-direction is the same.

Output

The output contains a single integer equal to the number of pairs of points which are exactly 2018 length units apart.

Sample input

4
20180000 20180000
20180000 20182018
20182018 20180000
20182018 20182018

Output

4

Here is my code

import java.util.*;
class Coordinates {
 int x;
 int y;
 public Coordinates(int x,int y) {
 this.x=x;
 this.y=y;
 }
 public double distanceWith(Coordinates z) {
 return Math.hypot((x-z.x),(y-z.y));
 }
}
class GreetingCard {
 public static void main(String [] args) {
 Scanner sc = new Scanner(System.in);
 HashSet<Coordinates> set = new HashSet<>();
 int count = sc.nextInt();
 int total = 0;
 for (int i=0;i<count;i++) {
 int x = sc.nextInt();
 int y = sc.nextInt();
 Coordinates curr = new Coordinates(x,y);
 if (i!=0) {
 total+=findDistances(curr, set);
 }
 set.add(curr);
 }
 System.out.println(total);
 }
 public static int findDistances(Coordinates curr, HashSet<Coordinates> set) {
 int total = 0;
 for (Coordinates inside : set) {
 if (inside.distanceWith(curr)==2018) {
 total+=1;
 }
 }
 return total;
 }
}

Answer 1

Calculating the distance between each pair of points is expensive. Since the coordinates are all integers, you can first calculate which delta-x and delta-y can lead to the distance 2018 at all. Define a function candidates(point, set) that filters the possible candidates. To do this efficiently, group the points by their x coordinate. Then, for a given x, you only have to look at a few of these groups.

Grouping the points improves performance because grouping has complexity around \$\mathcal O(n)\$, where \$n\$ is the number of points.

Afterwards, finding the candidate points is a simple lookup: for each delta in (-2018, -1680, -1118, 0, 1118, 1860, 2018) you need one lookup, which again sums up to \$\mathcal O(n)\$.

In summary, the number of comparisons will be much less than the \$n\cdot n\$ from your current code.

• Prashin Jeevaganth: Strictly speaking, how would you know if a particular arithmetic operation is expensive, after all a comparison is still made even in the filtering process that you suggested, why would it make such a big difference?
• Roland Illig: I expanded my answer a bit.