Editorial for COCI '07 Contest 2 #6 Pravokutni

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We need to find an algorithm of complexity better than $\mathcal O(N^3)$ ~\mathcal O(N^3)~. Here we will describe three such algorithms.

The basic idea of the first one is: choose the point in which the angle will be right, fix one other point in the triangle and quickly calculate how many of the remaining points form a right triangle with the first two points. The algorithm is based on the so-called canonical representation of a line. Each line can be, regardless of which two points it is generated from, transformed into a unique form. For a pair of points, we use the usual formulas to calculate three integers $A$ ~A~, $B$ ~B~ and $C$ ~C~ such that $Ax + By + C = 0$ ~Ax + By + C = 0~. The equation can be multiplied by a constant, because this doesn't change the line it represents. Now divide $A$ ~A~, $B$ ~B~ and $C$ ~C~ by their greatest common divisor so that they become relatively prime, and also negate the entire equation if the first non-zero number is negative. With this, we can build a function/map $f(line)$ ~f(line)~, which tells us how many points are on a line. Now it is easy to implement the idea from the start of this paragraph, and using appropriate data structures, the complexity will be good.

The second algorithm, after choosing the first point (where the right angle will be), sorts the remaining points around it by angle. Now we can use two variables (the so-called "sweep" method) to count all right triangles. We move the first variable point by point, and have the second one $90^\circ$ ~90^\circ~ ahead of it, moving forward, trying to form right triangles with the first variable.

The third algorithm is different from the first two, but also easier to implement. Choose a point $P$ ~P~ and translate the coordinate plane so that the point $P$ ~P~ is the origin (more precisely, subtract the coordinates of point $P$ ~P~ from every point). Now, for each point, first determine which quadrant it is in, and then rotate it by $90^\circ$ ~90^\circ~ until it is in the first quadrant. After that, sort all points by angle ( $y/x$ ~y/x~). Two points form a right triangle with point $P$ ~P~ if they have the same angle and if they were in neighbouring quadrants before rotating. After sorting, for each set of points with the same angle, count how many of them were in each of the four quadrants and multiply the numbers for neighbouring quadrants.

The complexity of all three algorithms is $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~.

Comments

There are no comments at the moment.