Problems
사각형은 볼록 사각형(왼)과 오목 사각형(오)으로 구분할 수 있다.
N개의 점이 평면상에 주어진다. 이때 어느 세 점도 한 직선 위에 있지 않다.
만들 수 있는 NC4개의 사각형들을 아래의 기준에 따라 점수를 부여하고, 모든 사각형의 점수의 합을 출력하시오.
볼록사각형이면서 넓이가 정확히 a라면 4점을 부여한다.
오목사각형이면서 넓이가 정확히 a라면 3점을 부여한다.
볼록사각형이면서 넓이가 정확히 a보다 크다면 2점을 부여한다.
오목사각형이면서 넓이가 정확히 a보다 크다면 1점을 부여한다.
이때 a는 만들 수 있는 가장 작은 사각형의 넓이로 정의한다.
Input
첫 줄에 점의 개수 N(4<=N<=1000)이 주어진다.
그 이후 N개의 줄에 걸쳐 점의 좌표 (xi, yi)가 공백으로 구분되어 주어진다. 이때 모든 좌표는 -10^9 이상 10^9 이하이다.
Output
만들 수 있는 모든 사각형에 대해 점수의 합을 출력하시오.
Example #1
4
0 0
1 0
0 1
1 1
4
Example #2
4
0 0
10 0
5 10
5 8
5
Example #3
4
0 0
10 0
5 10
5 3
7
Example #4
5
0 0
0 5
5 0
5 5
4 2
14
Source
ICPC 2019 Asia Regional – Seoul Problem F
You must sign in to write code.