4389 : 사각형
- 제한시간
- 2000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 0 회
- 시도횟수
- 0 회
문제
사각형은 볼록 사각형(왼)과 오목 사각형(오)으로 구분할 수 있다.
N개의 점이 평면상에 주어진다. 이때 어느 세 점도 한 직선 위에 있지 않다.
만들 수 있는 NC4개의 사각형들을 아래의 기준에 따라 점수를 부여하고, 모든 사각형의 점수의 합을 출력하시오.
- 볼록사각형이면서 넓이가 정확히 a라면 4점을 부여한다.
- 오목사각형이면서 넓이가 정확히 a라면 3점을 부여한다.
- 볼록사각형이면서 넓이가 정확히 a보다 크다면 2점을 부여한다.
- 오목사각형이면서 넓이가 정확히 a보다 크다면 1점을 부여한다.
이때 a는 만들 수 있는 가장 작은 사각형의 넓이로 정의한다.
입력형식
첫 줄에 점의 개수 N(4<=N<=1000)이 주어진다.
그 이후 N개의 줄에 걸쳐 점의 좌표 (xi, yi)가 공백으로 구분되어 주어진다. 이때 모든 좌표는 -10^9 이상 10^9 이하이다.
출력형식
만들 수 있는 모든 사각형에 대해 점수의 합을 출력하시오.
입력 예복사하기 4 0 0 1 0 0 1 1 1 |
출력 예복사하기 4 |
입력 예복사하기 4 0 0 10 0 5 10 5 8 |
출력 예복사하기 5 |
입력 예복사하기 4 0 0 10 0 5 10 5 3 |
출력 예복사하기 7 |
입력 예복사하기 5 0 0 0 5 5 0 5 5 4 2 |
출력 예복사하기 14 |