시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 1 0 0 0.000%

문제

After many years you and your coauthor H. Addaway have finally 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 find a suitable location to construct this scientific 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 deflects 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 find 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 \leq n \leq 5000$), the number of abandoned mine shafts.
  • $n$ lines, each with two integers $x$ and $y$ ($-10^8 \leq x, y\leq 10^8$), 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

예제 출력 1

1

예제 입력 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

예제 출력 2

15

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2020 Preliminaries E번

  • 문제를 만든 사람: Mike de Vries, Timon Knigge