볼록 정다각형

시간 제한1초메모리 제한128 MB

요약

정다각형의 세 꼭짓점 좌표가 주어질 때 가능한 정다각형의 최소 변의 수를 구하는 문제입니다.

문제

볼록 정다각형은 모든 변의 길이가 같고, 모든 내부각의 크기가 같으며, 각 내부각이 $180^\circ$ 보다 작은 다각형입니다. 예를 들어 정사각형은 볼록 정다각형입니다.

어떤 볼록 정다각형 $R$ 의 서로 다른 세 꼭짓점의 좌표가 주어집니다. 이 세 점을 모두 꼭짓점으로 가지는 볼록 정다각형 중에서, 꼭짓점의 개수가 가장 적은 경우의 꼭짓점 개수를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 세 줄로 구성되며, 각 줄에는 볼록 정다각형 $R$ 의 한 꼭짓점 $(x_i, y_i)$ 가 주어집니다 ( $-10^4 \le x_i, y_i \le 10^4$ ).

각 좌표는 실제 값과의 오차가 최대 $10^{-6}$ 입니다. 임의의 두 점 사이의 거리는 항상 최소 $1$ 이며, $R$ 의 꼭짓점 개수는 최대 $1000$ 개입니다.

입력의 마지막 줄에는 END가 주어지며, 이는 입력의 끝을 나타냅니다.

각 테스트 케이스마다 볼록 정다각형 $R$ 가 가질 수 있는 꼭짓점 개수의 최솟값을 한 줄에 하나씩 출력하세요.

예제 1

입력

-1385.736326 -146.954822
430.000292 -2041.361203
1162.736034 478.316025
0.000000 4147.000000
-4147.000000 0.000000
0.000000 -4147.000000
END

예상 출력

3
4

예제 2

입력

1000.000000 0.000000
0.000000 1000.000000
-1000.000000 0.000000
END

예상 출력