Visibility
Time limit2sMemory limit512 MB
Given N grid points, count ordered pairs (X, Y) such that Y lies strictly inside the 60 degree wedge opening south from X.
- Level
Medium6 of 10
- Topics
- Geometry, Sorting, Binary search, Math
- Solved
- No attempts yet
Problem
In the Regional Park of the Haute Vallée de Chevreuse, N observation houses have been built so that the local animals can be watched and counted. To help animals and tourists move more efficiently, paths were built along the axes of a grid: these paths all run straight along the vertical lines (the North-South axis) and the horizontal lines (the West-East axis).
Every house has a wide observation window that faces South. Through this window one can see in every direction within a 60 degree angle of South, covering a third of the plane, which makes for a fine sight in spring and summer. In winter, however, the animals stay home or migrate to warmer countries, and the trees have lost their leaves and become so thin that they are barely visible, so the only things one can see and count are the other observation houses.
Still, this is a fun excursion into the wild for the days after SWERC. A group of N students has decided to go to the Regional Park. You are helping them with the planning, and you have the coordinates of every house. Each student goes to one of the houses.
Once arrived, each participant plans to stand at the observation window of her own house and take a picture of every other house she can see from that spot. After the excursion, you will have to gather all the pictures that the students have taken.
Given the list of coordinates of the observation houses, how many pictures will you gather?
Input
The input consists of the following lines:
- The first line contains the number N of students, which is also the number of observation houses, an integer;
- For all i such that 0 ≤ i < N, line i + 2 contains the coordinates Xi and Yi of the ith observation house, separated by a space.
Output
Your output should contain a single line with a single integer equal to the total number of pictures that will be taken.
Constraints
- 2 ≤ N ≤ 100 000;
- 0 ≤ Xi ≤ 100 000 and 0 ≤ Yi ≤ 100 000 for all i.
Notes
If a house Y lies on the border of the third of the plane visible from another house X, the participant who went to house X will not take a picture of Y, as this picture would only be partial. If a house Z lies on the segment [X,Y] when Y is visible from X, then the participant who went to house X will take one picture focusing only on house Y, and another picture focusing only on house Z.