프로그램 명: coci_sir
제한시간: 1 초

Kreso has bought some delicious cheese with peppers, but Stjepan doesn’t really like peppers so he’s trying to cut a piece that doesn’t contain any peppers.

Kreso’s cheese has the shape of a convex polygon, and each pepper is one point on the inside of the polygon. Stjepan cuts the cheese exactly once in such a way that he chooses two vertices of the polygon that are not adjacent and cuts along the line segment connecting them. Stjepan then takes the freshly cut part without any peppers (on the inside nor on the edges).

  • Write a programme that will determine whether Stjepan can cut a piece of cheese without any peppers. If he can, determine the maximum possible area of the piece of cheese without peppers that Stjepan can cut.

    입력

    The polygon vertices are given in counter-clockwise order and form a convex polygon. None two adjacent edges are parallel.

    All peppers are located in different coordinates in the inside of the polygon (they will not be located on the edge or outside of the polygon).

    출력

    The first and only line of output must contain an integer - twice the maximum possible area (the double area is always going to be an integer).

    If it isn’t possible to cut a piece of cheese without peppers in one move, output 0.

    입출력 예

    입력

5
0 1
3 0
4 2
2 3
0 3
3
2 1
3 1
3 2

출력

4

입력

6
-3 3
-3 -4
-2 -5
2 -5
3 -4
3 3
7
1 0
0 -1
0 -3
2 0
0 0
0 2
-1 0

출력

10 

입력

6
0 3
-1 2
-1 -2
0 -3
1 -2
1 2
1
0 0

출력

4

Clarification of the second example: Stjepan cuts from vertex 2 to vertex 5.
Clarification of the third example: Stjepan cuts from vertex 1 to vertex 3.

    출처:2013-2014 olympiad 4/4
    [질/답] [제출 현황] [푼 후(0)]
    [ 채 점 ] [홈으로]  [뒤 로]