네 개의 점

시간 제한3초메모리 제한256 MB

요약

네 점이 주어질 때, 각 변에 정확히 하나씩(꼭짓점 제외) 점이 놓이는 정사각형이 존재하는지 판별합니다.

난이도: 어려움10점 중 8점
유형: 기하, 수학, 이분 탐색
정답자: 아직 제출이 없습니다

문제

마이크는 마술사입니다. 그의 발명품 중 하나는 통과하는 모든 사람에게 초자연적인 능력을 부여하는 미궁입니다. 미궁의 내부 구조는 매우 복잡하지만, 밖에서 보면 땅 위에 그려진 하나의 정사각형일 뿐입니다.

마이크는 바닷가에서 미궁을 놓기에 알맞은 장소를 찾았습니다. 그는 모래 위에 정사각형의 경계를 그리고, 작은 돌 네 개로 네 점을 표시했습니다. 이때 정사각형의 각 변에는 정확히 하나의 돌이 놓이고, 어떤 돌도 꼭짓점에는 놓이지 않았습니다.

모래 위의 그림은 오래가지 않아, 얼마 뒤 마이크에게는 제자리에 있는 돌 네 개만 남았습니다. 그는 표시했던 정사각형이 과연 존재할 수 있었는지 궁금합니다. 다시 말해, 네 변이 각각 돌 하나씩을 (꼭짓점이 아닌) 내부에 포함하는 정사각형이 하나라도 있는지 알고 싶습니다. 바닷가는 평면이고 돌은 그 위의 점이라고 가정합니다.

네 돌의 위치가 주어질 때, 그러한 정사각형이 존재하는지 판별하세요.

입력

네 줄이 주어지며, $i$ 번째 줄에는 두 정수 $x_i$ 와 $y_i$ 가 주어집니다. 이는 $i$ 번째 돌의 좌표입니다 ( $-1000 \le x_i, y_i \le 1000$ ). 어떤 두 돌도 같은 위치에 있지 않으며, 어떤 세 돌도 한 직선 위에 있지 않습니다.

출력

네 변이 각각 정확히 하나의 돌을 내부에 포함하는(꼭짓점에는 어떤 돌도 없는) 정사각형이 존재하면 $1$ 을, 그러한 정사각형이 존재하지 않으면 $0$ 을 한 줄에 출력하세요.

예제4

예제 1
입력
```
6 13
11 12
9 2
2 6
```
예상 출력
```
1
```
예제 2
입력
```
0 0
5 5
5 0
3 2
```
예상 출력
```
0
```
예제 3
입력
```
3 0
10 4
7 10
0 6
```
예상 출력
```
1
```
예제 4
입력
```
245 -49
210 62
125 239
-77 16
```
예상 출력
```
0
```