문제
정올시는 최근에 광역시로 승격되면서, 엄청나게 큰 도시가 되었다.
정올광역시장이 된 민재는 도시의 위상을 높이기 위해, 공항을 건설하려고 한다.
정올광역시는 볼록다각형 모양으로 생겼고, 그 안에는 여러 채의 아파트가 있다.
아파트는 전체적인 도시의 규모를 생각하면 너무 작아서, 점 하나로 생각한다.
민재는 공항을 건설하기 위한 땅을 확보하려고 한다.
땅의 확보는 다음과 같이 이루어진다.
- 볼록다각형의 두 꼭지점을 골라서, 그 두 점을 잇는다.
- 그러면 볼록다각형이 두 점을 이은 선분을 중심으로 두 다각형으로 쪼개지는데, 만약 그 둘 중에서 아파트를 한 채도 포함하지 않는 다각형이 있다면, 그 다각형은 공항 부지로 적합하다고 한다. 참고로 점이 다각형에 점이 다각형의 경계에 위치한 경우도 포함한다.
- 공항 부지로 적합한 다각형 중 그 면적이 가장 큰 다각형을 최종적으로 공항 부지로 정한다.
예를 들어 정올광역시의 도면이 그림 1과 같다고 가정해 보자. 여기에서 파란색 점은 아파트를 나타낸다.
그림 1
이 경우에는, 점선을 기준으로 왼쪽 삼각형이 아파트를 하나도 포함하지 않고 있으므로, 공항 부지로써 적합하게 된다. (1,6)과 (5,5)를 잇는 선분으로 나누는 방법도 존재하지만, 넓이가 예시의 경우보다 넓지 않다.
정올광역시 경계의 각 꼭지점 좌표와, 정올광역시에 존재하는 모든 아파트의 좌표가 주어질 때, 공항 부지로써 가능한 면적의 최댓값을 구하는 프로그램을 작성하라.
입력
첫 줄에 정올광역시의 경계를 이루는 볼록다각형의 꼭지점 수인 N이 주어진다.
다음 N줄에 걸쳐, 각 꼭지점들의 좌표가 xi yi 형식으로 주어진다. 주어지는 순서는 항상 시작 좌표부터 반시계 방향이다.
다음 줄에 아파트의 수인 M이 주어진다.
다음 M줄에 걸쳐, 각 아파트의 좌표가 xi yi 형식으로 주어진다. 모든 아파트는 정올광역시의 경계 안에 있다.
(단 경계선 위에 아파트가 있는 경우는 없다.)
부분문제의 제약 형식
모든 부분문제에서 4≤N≤300,000 , 1≤M≤300,000이다.
모든 부분문제에서 좌표값으로 주어지는 값 xi yi에 대해, -109≤xi,yi≤109를 만족한다.
모든 입력값은 정수이다.
출력
첫 줄에, 공항 부지 면적의 최댓값×2를 출력한다.
출력값은 당연히 항상 정수이다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 17점 | N≤300, M≤300 |
| #2 | 33점 | N≤3,000, M≤3,000 |
| #3 | 50점 | 주어진 제약조건 외에 아무 제약조건이 없다. |
예제 #1
5
1 4
4 3
5 5
3 6
1 6
3
3 4
4 4
4 5
4
예제 #2
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
예제 #3
6
0 3
-1 2
-1 -2
0 -3
1 -2
1 2
1
0 0
4
로그인해야 코드를 작성할 수 있어요.