정올시는 최근에 광역시로 승격되면서, 엄청나게 큰 도시가 되었다.

정올광역시장이 된 민재는 도시의 위상을 높이기 위해, 공항을 건설하려고 한다.

정올광역시는 볼록다각형 모양으로 생겼고, 그 안에는 여러 채의 아파트가 있다.

아파트는 전체적인 도시의 규모를 생각하면 너무 작아서, 점 하나로 생각한다.

민재는 공항을 건설하기 위한 땅을 확보하려고 한다.

땅의 확보는 다음과 같이 이루어진다.

- 볼록다각형의 두 꼭지점을 골라서, 그 두 점을 잇는다.

- 그러면 볼록다각형이 두 점을 이은 선분을 중심으로 두 다각형으로 쪼개지는데, 만약 그 둘 중에서 아파트를 한 채도 포함하지 않는 다각형이 있다면, 그 다각형은 공항 부지로 적합하다고 한다. 참고로 점이 다각형에 점이 다각형의 경계에 위치한 경우도 포함한다.

- 공항 부지로 적합한 다각형 중 그 면적이 가장 큰 다각형을 최종적으로 공항 부지로 정한다.

예를 들어 정올광역시의 도면이 그림 1과 같다고 가정해 보자. 여기에서 파란색 점은 아파트를 나타낸다.

그림 1

이 경우에는, 점선을 기준으로 왼쪽 삼각형이 아파트를 하나도 포함하지 않고 있으므로, 공항 부지로써 적합하게 된다. (1,6)과 (5,5)를 잇는 선분으로 나누는 방법도 존재하지만, 넓이가 예시의 경우보다 넓지 않다.

정올광역시 경계의 각 꼭지점 좌표와, 정올광역시에 존재하는 모든 아파트의 좌표가 주어질 때, 공항 부지로써 가능한 면적의 최댓값을 구하는 프로그램을 작성하라.

공항 부지 확보하기 timer 2s memory 512MB

공항 부지 확보하기 2s 512MB