ICPC 2019 Asia Regional – Seoul Problem F- 사각형 > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP