CCOQR '16 - Stupendous Bowties - Olympiads Online Judge

CCOQR '16 - Stupendous Bowties

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.4s

Memory limit: 64M

Author:

SourSpinach

Problem types

There are $N$ ~N~ $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~ distinct points on a 2D plane, with the $i^{th}$ ~i^{th}~ one at integral coordinates $(x_i, y_i)$ ~(x_i, y_i)~ $(-10^9 \le x_i \le 10^9, -10^9 \le y_i \le 10^9)$ .

A Fantastic Right Triangle is one which uses 3 of the given points as its vertices, is non-degenerate (i.e., has positive area), and which has both of its legs axis-aligned (one of its two shortest sides is horizontal and the other shortest side is vertical). The vertex at which the two legs of such a triangle meet (which has an interior right angle) is known as the triangle's Spectacular Vertex.

A Stupendous Bowtie consists of an unordered pair of Fantastic Right Triangles which share the same point as their Spectacular Vertex, and which touch only at that point. Count the number of Stupendous Bowties which exist amongst the given points.

Subtasks

For 2 of the 15 marks available, $N \le 20$ ~N \le 20~.
For another 3 of the 15 marks available, $N \le 200$ ~N \le 200~.
For another 2 of the 15 marks available, $N \le 2\,000$ ~N \le 2\,000~.
For another 3 of the 15 marks available, $N \le 100\,000$ ~N \le 100\,000~, $-10^5 \le x_i \le 10^5$ ~-10^5 \le x_i \le 10^5~, and $-10^5 \le y_i \le 10^5$ ~-10^5 \le y_i \le 10^5~.

Input Specification

The first line of the input contains one integer, $N$ ~N~. The remaining $N$ ~N~ lines each contain two integers, $x_i$ ~x_i~ and $y_i$ ~y_i~ for $i = 1 \dots N$ ~i = 1 \dots N~.

Output Specification

Output a single integer, the number of Stupendous Bowties which exist amongst the given points. Note that this value may not fit in a 32-bit signed integer, and may need to be stored in a long long / long / int64 variable in C++ / Java / Pascal, respectively.

Sample Input

12
-3 6
1 6
-1 4
-3 2
1 2
4 2
-4 -3
-3 -3
1 -3
-1 -4
1 -4
-3 -6

Output for Sample Input

Explanation for Output for Sample Input

The diagram below illustrates the set of given points (represented by the 12 blue dots), with one of the eight possible Stupendous Bowties shown in red.

$\text{[math]}$

Comments

4

println_hi_ commented on Nov. 24, 2016, 12:28 p.m. ← edit 6 →

I have two versions of an algorithm for this which takes $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~ time and $\mathcal{O}(N)$ ~\mathcal{O}(N)~ space. However neither version can pass test case 21 without a MLE or a TLE. I feel as this algorithm would pass if written in a faster language such as C++ and I am sure I have the lowest possible space and time complexity.

I know there are some solutions which AC are written in Python, presumably because they are faster by a constant factor. Could someone please give me some advice on how to speed up my code? (I have already implemented FastIO and PyPy3 causes such a significant memory issue that I fail the first test case)

4

Xyene commented on Nov. 24, 2016, 4:18 p.m.

Your submission passes as-is in Python 2. Python 3 is typically slower than Python 2 for contest scenarios.

3

println_hi_ commented on Nov. 25, 2016, 12:50 a.m.

Ah thank you very much, that's very interesting. I'll have to research why.