민코프스키 합

다각형은 경계 위의 모든 점과 내부의 모든 영역을 포함한다. 이 문제에서 다루는 다각형은 다음 조건을 모두 만족한다.

1. 다각형 안의 임의의 두 점을 잇는 선분이 항상 다각형 안에 완전히 포함된다.
2. 꼭짓점이 세 개 이상이다.
3. 세 꼭짓점이 한 직선 위에 놓이는 경우가 없다.

두 다각형 A와 B가 위 조건을 만족한다고 하자. A에 속한 한 점의 좌표를 (x1, y1), B에 속한 한 점의 좌표를 (x2, y2)라고 할 때, 가능한 모든 점 (x1 + x2, y1 + y2)가 이루는 도형을 두 다각형의 민코프스키 합이라고 한다.

두 다각형이 주어졌을 때, 두 다각형의 민코프스키 합을 구하는 프로그램을 작성하시오. 만약 조건을 만족하는 출력 다각형이 여러 개라면 다음 우선순위에 따라 하나만 출력한다. 번호가 작을수록 우선순위가 높다.

1. 꼭짓점의 개수가 가장 작은 것
2. 면적이 가장 작은 것
3. 다각형을 이루는 모든 좌표 중 최소 x좌표가 가장 작은 것
4. 다각형을 이루는 모든 좌표 중 최소 y좌표가 가장 작은 것

첫째 줄에 두 다각형 A와 B의 꼭짓점 개수 N과 M이 주어진다. (3 <= N, M <= 1,000)

다음 N개의 줄에는 다각형 A의 꼭짓점 좌표가 주어진다. 이어지는 M개의 줄에는 다각형 B의 꼭짓점 좌표가 주어진다. 각 좌표는 x좌표와 y좌표가 공백으로 구분되어 주어지며, 꼭짓점은 반시계 방향 순서로 입력된다.

모든 좌표는 100,000,000을 넘지 않는 음이 아닌 정수이다.

첫째 줄에 구한 다각형의 꼭짓점 개수를 출력한다.

다음 줄부터 다각형을 이루는 꼭짓점의 x좌표와 y좌표를 한 줄에 하나씩 반시계 방향으로 출력한다. 출력의 첫 번째 꼭짓점은 x좌표가 가장 작은 점이어야 한다. 그런 점이 여러 개라면 그중 y좌표가 가장 작은 점을 첫 번째로 출력한다.

민코프스키(Minkowski, Hermann. 18641909)는 독일에서 활동한 러시아 수학자로, 기하학에 공리계를 도입한 것으로 알려진 힐베르트(Hilbert, David. 18621943)와 교류하며 괴팅겐 대학을 세계 수학의 중심지로 만드는 데 함께했다. 괴팅겐 대학은 20세기에 막스 보른, 제임스 프랑크, 베르너 하이젠베르크, 막스 폰 라우에 같은 현대물리학의 대가들을 배출했다. 민코프스키 또한 <공간과 시간> 등의 저서에서 4차원 시공간을 논하며 아인슈타인의 상대성이론 형성에 공헌한 것으로 알려져 있다.