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




4389 : Quadrilaterals

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

A quadrilateral is a polygon with exactly four distinct corners and four distinct sides, without any crossing between its sides. A quadrilateral is called convex if all the inner angles at its corners are less than 180 degrees, or called non-convex, otherwise. See the illustration below for a convex quadrilateral (left) and a non-convex quadrilateral (right).

 

 


 

 

In a test problem, you are given a set P of n points in the plane, no three of which are collinear, and asked to find as many quadrilaterals as possible by connecting four points from P, while each point in P can be used limitlessly many times and those quadrilaterals you find may freely overlap each other. You will earn different credits for each quadrilateral you find, depending on its shape and area. In principle, you earn more credits for convex quadrilaterals and for quadrilaterals with minimum area.

 

More precisely, the rules for credits are as follows, where a denotes the minimum over the areas of all possible quadrilaterals formed by connecting four points in P:

 

 



  • For each distinct convex quadrilateral with area exactly a, you earn 4 credits.

  • For each distinct non-convex quadrilateral with area exactly a, you earn 3 credits.

  • For each distinct convex quadrilateral with area strictly larger than a, you earn 2 credits.

  • For each distinct non-convex quadrilateral with area strictly larger than a, you earn 1 credit.


 

 

Note that two quadrilaterals are distinct unless the corners and sides of one are exactly the same to the other’s, and that there may be two or more quadrilaterals of the minimum area a.

 

You of course want to find all possible quadrilaterals and earn the maximum possible total credits. Given a set P of n points in the plane, write a program that outputs the maximum possible total credits you can earn when you find all possible quadrilaterals from the set P.​ 


입력형식

Your program is to read from standard input. The input starts with a line containing an integer n (4 ≤ n ≤ 1,000), where n denotes the number of points in the set P. In the following n lines, each line consists of two integers, ranging −109 to 109, representing the coordinates of a point in P. There are no three points in P that are collinear.

 


출력형식

Your program is to write to standard output. Print exactly one line consisting of a single integer that represents the maximum possible total credits you can earn from the set P. 


입력 예

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