아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

다각형의 합

시간 제한1초메모리 제한128 MB

요약
두 볼록 다각형의 민코프스키 합을 구하고 그 결과 다각형 넓이의 두 배를 출력한다.
난이도

어려움10점 중 8점

유형
기하, 투 포인터, 정렬, 구현
정답자
아직 제출이 없습니다

문제

두 볼록 다각형 AA와 BB에 대해, 두 다각형의 합 A+BA + B를 다음과 같이 정의한다.

A+B={ p1+p2:p1∈A, p2∈B }.A + B = \{\, p_1 + p_2 : p_1 \in A,\ p_2 \in B \,\}.

즉, A+BA + B는 AA의 한 점과 BB의 한 점을 더해서 얻을 수 있는 모든 점의 집합이며, 이 집합 또한 볼록 다각형이 된다.

예를 들어 AA의 꼭짓점이 (0,0)(0, 0), (0,2)(0, 2), (2,0)(2, 0)이고 BB의 꼭짓점이 (0,0)(0, 0), (0,1)(0, 1), (3,0)(3, 0)이면, A+BA + B는 꼭짓점이 (0,0)(0, 0), (0,3)(0, 3), (3,2)(3, 2), (5,0)(5, 0)인 볼록 다각형이고 그 넓이는 9.59.5이다.

두 볼록 다각형 AA와 BB를 입력받아 A+BA + B의 넓이를 구하고, 그 넓이의 두 배를 출력하라. 모든 좌표가 정수이므로 넓이의 두 배는 항상 정수이다.

입력

첫째 줄에 두 정수 nn과 mm이 주어진다 (3≤n,m≤100 0003 \le n, m \le 100\,000). 각각 다각형 AA와 BB의 꼭짓점 개수이다.

둘째 줄에 nn개의 정수 쌍 xi yix_i\ y_i가 주어진다 (−108≤xi,yi≤108-10^8 \le x_i, y_i \le 10^8). 다각형 AA의 꼭짓점을 시계 방향 순서로 나열한 것이다.

셋째 줄에 mm개의 정수 쌍 xi yix_i\ y_i가 주어진다 (−108≤xi,yi≤108-10^8 \le x_i, y_i \le 10^8). 다각형 BB의 꼭짓점을 시계 방향 순서로 나열한 것이다.

출력

A+BA + B의 넓이의 두 배를 정수 하나로 출력한다.

예제6

  1. 예제 1

    입력
    4 4
    0 0 0 1 2 1 2 0
    0 0 0 2 1 2 1 0
    
    예상 출력
    18
    
  2. 예제 2

    입력
    3 3
    0 0 0 2 2 0
    0 0 0 1 3 0
    
    예상 출력
    19
    
  3. 예제 3

    입력
    4 4
    0 0 0 1 1 1 1 0
    0 0 0 1 1 1 1 0
    
    예상 출력
    8
    
  4. 예제 4

    입력
    3 4
    0 3 3 0 0 0
    0 2 2 2 2 0 0 0
    
    예상 출력
    41
    
  5. 예제 5

    입력
    4 3
    -2 2 2 2 2 -2 -2 -2
    -1 1 1 -1 -1 -1
    
    예상 출력
    68
    
  6. 예제 6

    입력
    6 3
    0 4 2 4 3 2 2 0 0 0 -1 2
    1 2 2 0 0 0
    
    예상 출력
    52