After many years you and your coauthor H. Addaway have fifinally developed a Theory of Everything that explains everything: Why does time have a direction? How should quantum mechanics be interpreted? What caused the Big Bang? What is love?
An unfortunate fact about physics is that physical theories need to be experimentally tested. In particular, your theory rests on the discovery of so called Barely Audible Particle Clusters(BAPCs). For this purpose you have proposed the development of a Large Eightgon Collider. What remains is to fifind a suitable location to construct this scientifific wonder.
For obvious reasons, the Large Eightgon Collider must consist of eight straight tunnels that together form an underground cycle. Each tunnel is allowed to have a different non-zero length. At each of the eight tunnel connections, a special detector must be built, that also slightly deflflects the particles 45 degrees to the left. Each of the eight detectors attracts many researchers, requiring a shaft to the surface to supply them with fresh food and oxygen.
In order to save costs, they will reuse abandoned mine shafts. Given a map of all abandoned mine shafts, your job is to fifind the number of possible locations to build this miracle. You only consider locations where at least one tunnel runs parallel to the x-axis of the map.
Figure E.1 shows the second sample.
Figure E.1: Visualisation of Sample 2 showing one possible location for the Large Eightgon Collider
输入描述:
The input consists of:
• A line with an integer n (1 ≤ n ≤ 5000), the number of abandoned mine shafts.
• n lines, each with two integers x and y (−108 ≤ x, y ≤ 108), the coordinates of the abandoned mine shafts.
输出描述:
Output the number of possible locations to build the Large Eightgon Collider.
示例1
输入
复制
8
0 1
1 0
0 2
2 0
3 1
1 3
3 2
2 3
示例2
输入
复制
21
0 1
0 2
0 3
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 1
4 2
4 3