2244번 - 민코프스키 합 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 679 | 273 | 208 | 41.026% |
문제
다각형은 그 경계 위에 놓인 모든 점과 그 안의 모든 영역으로 구성되어 있다. 이러한 다각형 중에서 앞으로 이 문제에서 다룰 다각형은 다음과 같은 특성을 만족하는 것으로 한다.
- 다각형 안의 임의의 두 점을 잇는 선분이 완전히 그 다각형 안에 속해 있다.
- 세 개 이상의 꼭짓점으로 이루어져 있다.
- 세 꼭짓점이 한 직선 위에 있는 경우는 없다.
이러한 특성을 만족하는 두 다각형 A, B가 있을 때, 이들의 민코프스키(Minkowski) 합은, A에 속하는 모든 영역의 좌표 (x1, y1)와 B에 속하는 모든 영역의 좌표 (x2, y2)에 대해, 있을 수 있는 모든 (x1 + x2, y1 + y2) 조합이 나타내는 영역의 도형이다. 다음은 두 삼각형과 이들의 민코프스키 합을 그림으로 나타낸 것이다.
두 다각형이 주어졌을 때, 두 다각형의 민코프스키 합을 구하는 프로그램을 작성하시오. 만약 민코프스키 합이 여러 개의 다각형으로 이루어진다면 다음의 우선순위에 따라 하나의 다각형만을 구하도록 한다. 번호가 작은 것이 우선순위가 높은 것이다.
- 꼭짓점의 개수가 가장 작은 것
- 면적이 가장 작은 것
- 다각형을 이루는 모든 좌표들 중 최소 x좌표가 가장 작은 것
- 다각형을 이루는 모든 좌표들 중 최소 y좌표가 가장 작은 것
입력
첫째 줄에 두 다각형 A와 B의 꼭짓점 개수 N과 M이 주어진다. (3 ≤ N, M ≤ 1,000) 다음 N개의 줄에는 다각형 A를 이루는 꼭짓점의 좌표가, 그 다음 M개의 줄에는 다각형 B를 이루는 꼭짓점의 좌표가 주어진다. 좌표는 x좌표와 y좌표가 빈칸을 사이에 두고 순서대로 주어지며, 반시계 방향으로 입력된다. 모든 좌표는 100,000,000을 넘지 않는 음이 아닌 정수이다.
출력
첫째 줄에 우리가 구하고자 하는 다각형의 꼭짓점의 개수를 출력한다. 다음 줄부터는 다각형을 이루는 꼭짓점의 x좌표와 y좌표를 한 줄에 한 쌍씩 반시계 방향으로 출력한다. 출력되는 첫 번째 꼭짓점은 x좌표가 가장 작은 점으로 하며, x좌표가 가장 작은 점이 여러 개 있을 경우 y좌표가 가장 작은 점으로 한다.
예제 입력 1
3 3 0 0 1 0 1 1 0 1 0 0 1 0
예제 출력 1
5 0 0 2 0 2 1 1 2 0 1
힌트
민코프스키(Minkowski, Hermann. 1864~1909)는 독일에서 활동한 러시아 수학자로 기하학에 공리계를 도입한 것으로 잘 알려진 힐베르트(Hilbert, David. 1862~1943)와 친교를 맺고 함께 괴팅켄 대학을 세계 수학의 중심지로 만들었다. 괴팅겐 대학은 20세기 들어 노벨상 수상자인 막스 보른, 제임스 프랑크, 베르너 하이젠베르크, 막스 폰 라우에 등 현대물리학의 대가들을 배출한 바 있으며 실제로 민코프스키 또한 <공간과 시간> 등의 저서에서 4차원적 시공간에 대해 논하며 아인슈타인의 상대성이론의 형성에도 공헌한 것으로 알려져 있다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호