시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 126 35 26 25.000%

문제

다각형은 그 경계 위에 놓인 모든 점과 그 안의 모든 영역으로 구성되어 있다. 이러한 다각형 중에서 앞으로 이 문제에서 다룰 다각형은 다음과 같은 특성을 만족하는 것으로 한다.

  1. 다각형 안의 임의의 두 점을 잇는 선분이 완전히 그 다각형 안에 속해 있다.
  2. 세 개 이상의 꼭짓점으로 이루어져 있다.
  3. 세 꼭짓점이 한 직선 위에 있는 경우는 없다.

이러한 특성을 만족하는 두 다각형 A, B가 있을 때, 이들의 민코프스키(Minkowski) 합은, 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좌표가 가장 작은 점으로 하며, 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차원적 시공간에 대해 논하며 아인슈타인의 상대성이론의 형성에도 공헌한 것으로 알려져 있다.

W3sicHJvYmxlbV9pZCI6IjIyNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiZmNcdWNmNTRcdWQ1MDRcdWMyYTRcdWQwYTQgXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhZGY4IFx1YWNiZFx1YWNjNCBcdWM3MDRcdWM1ZDAgXHViMTkzXHVjNzc4IFx1YmFhOFx1YjRlMCBcdWM4MTBcdWFjZmMgXHVhZGY4IFx1YzU0OFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjNjAxXHVjNWVkXHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWIyZTRcdWFjMDFcdWQ2MTUgXHVjOTExXHVjNWQwXHVjMTFjIFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YjJlNFx1YjhmMCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQyYjlcdWMxMzFcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViMmU0XHVhYzAxXHVkNjE1IFx1YzU0OFx1Yzc1OCBcdWM3ODRcdWM3NThcdWM3NTggXHViNDUwIFx1YzgxMFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzc0IFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWFkZjggXHViMmU0XHVhYzAxXHVkNjE1IFx1YzU0OFx1YzVkMCBcdWMxOGRcdWQ1NzQgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMzggXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTM4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NCBcdWQ1NWMgXHVjOWMxXHVjMTIwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHVkMmI5XHVjMTMxXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHViMmU0XHVhYzAxXHVkNjE1IEEsIEJcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViNGU0XHVjNzU4IFx1YmJmY1x1Y2Y1NFx1ZDUwNFx1YzJhNFx1ZDBhNChNaW5rb3dza2kpIFx1ZDU2OVx1Yzc0MCwgQVx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWM4OGNcdWQ0NWMgKHgxLCB5MSlcdWM2NDAgQlx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWM4OGNcdWQ0NWMgKHgyLCB5MilcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgKHgxK3gyLCB5MSt5MikgXHVjODcwXHVkNTY5XHVjNzc0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM2MDFcdWM1ZWRcdWM3NTggXHViM2M0XHVkNjE1XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGNcdWM3NDAgXHViNDUwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1YWNmYyBcdWM3NzRcdWI0ZTRcdWM3NTggXHViYmZjXHVjZjU0XHVkNTA0XHVjMmE0XHVkMGE0IFx1ZDU2OVx1Yzc0NCBcdWFkZjhcdWI5YmNcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwOFwvbWluLlBOR1wiIHN0eWxlPVwiaGVpZ2h0OjE1NnB4OyB3aWR0aDo0NzhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViYmZjXHVjZjU0XHVkNTA0XHVjMmE0XHVkMGE0IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViOWNjXHVjNTdkIFx1YmJmY1x1Y2Y1NFx1ZDUwNFx1YzJhNFx1ZDBhNCBcdWQ1NjlcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0XHViYTc0IFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWM2YjBcdWMxMjBcdWMyMWNcdWM3MDRcdWM1ZDAgXHViNTMwXHViNzdjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWI5Y2NcdWM3NDQgXHVhZDZjXHVkNTU4XHViM2M0XHViODVkIFx1ZDU1Y1x1YjJlNC4gXHViYzg4XHVkNjM4XHVhYzAwIFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NzQgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHVhYzAwIFx1YjE5Mlx1Yzc0MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4MzxcL2xpPlxyXG5cdDxsaT5cdWJhNzRcdWM4MDFcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjODM8XC9saT5cclxuXHQ8bGk+XHViMmU0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjXHViNGU0IFx1YzkxMSBcdWNkNWNcdWMxOGMgeFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4MzxcL2xpPlxyXG5cdDxsaT5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWI0ZTQgXHVjOTExIFx1Y2Q1Y1x1YzE4YyB5XHVjODhjXHVkNDVjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YjJlNFx1YWMwMVx1ZDYxNSBBXHVjNjQwIEJcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwIFx1YWMxY1x1YzIxOCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyZsdDs9TiwgTSZsdDs9MSwwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTUgQVx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTUgQlx1Yjk3YyBcdWM3NzRcdWI4ZThcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHViZTQ4XHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViYzE4XHVjMmRjXHVhY2M0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgMTAwLDAwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZiMFx1YjlhY1x1YWMwMCBcdWFkNmNcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWNcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NWMgXHVjMzBkXHVjNTI5IFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWI0MThcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgeFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzgxMFx1YzczY1x1Yjg1YyBcdWQ1NThcdWJhNzAsIHhcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM4MTBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHVhY2JkXHVjNmIwIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM4MTBcdWM3M2NcdWI4NWMgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJiZmNcdWNmNTRcdWQ1MDRcdWMyYTRcdWQwYTQoTWlua293c2tpLCBIZXJtYW5uLiAxODY0fjE5MDkpXHViMjk0IFx1YjNjNVx1Yzc3Y1x1YzVkMFx1YzExYyBcdWQ2NWNcdWIzZDlcdWQ1NWMgXHViN2VjXHVjMmRjXHVjNTQ0IFx1YzIxOFx1ZDU1OVx1Yzc5MFx1Yjg1YyBcdWFlMzBcdWQ1NThcdWQ1NTlcdWM1ZDAgXHVhY2Y1XHViOWFjXHVhY2M0XHViOTdjIFx1YjNjNFx1Yzc4NVx1ZDU1YyBcdWFjODNcdWM3M2NcdWI4NWMgXHVjNzk4IFx1YzU0Y1x1YjgyNFx1YzljNCBcdWQ3OTBcdWJjYTBcdWI5NzRcdWQyYjgoSGlsYmVydCwgRGF2aWQuIDE4NjJ+MTk0MylcdWM2NDAgXHVjZTVjXHVhZDUwXHViOTdjIFx1YjlmYVx1YWNlMCBcdWQ1NjhcdWFlZDggXHVhZDM0XHVkMzA1XHVjZjA0IFx1YjMwMFx1ZDU1OVx1Yzc0NCBcdWMxMzhcdWFjYzQgXHVjMjE4XHVkNTU5XHVjNzU4IFx1YzkxMVx1YzJlY1x1YzljMFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YWQzNFx1ZDMwNVx1YWM5MCBcdWIzMDBcdWQ1NTlcdWM3NDAgMjBcdWMxMzhcdWFlMzAgXHViNGU0XHVjNWI0IFx1YjE3OFx1YmNhOFx1YzBjMSBcdWMyMThcdWMwYzFcdWM3OTBcdWM3NzggXHViOWM5XHVjMmE0IFx1YmNmNFx1Yjk3OCwgXHVjODFjXHVjNzg0XHVjMmE0IFx1ZDUwNFx1Yjc5MVx1ZDA2YywgXHViY2EwXHViOTc0XHViMTA4IFx1ZDU1OFx1Yzc3NFx1YzgyMFx1YmNhMFx1Yjk3NFx1ZDA2YywgXHViOWM5XHVjMmE0IFx1ZDNmMCBcdWI3N2NcdWM2YjBcdWM1ZDAgXHViNGYxIFx1ZDYwNFx1YjMwMFx1YmIzY1x1YjlhY1x1ZDU1OVx1Yzc1OCBcdWIzMDBcdWFjMDBcdWI0ZTRcdWM3NDQgXHViYzMwXHVjZDljXHVkNTVjIFx1YmMxNCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVjMmU0XHVjODFjXHViODVjIFx1YmJmY1x1Y2Y1NFx1ZDUwNFx1YzJhNFx1ZDBhNCBcdWI2MTBcdWQ1NWMgJmx0O1x1YWNmNVx1YWMwNFx1YWNmYyBcdWMyZGNcdWFjMDQmZ3Q7IFx1YjRmMVx1Yzc1OCBcdWM4MDBcdWMxMWNcdWM1ZDBcdWMxMWMgNFx1Y2MyOFx1YzZkMFx1YzgwMSBcdWMyZGNcdWFjZjVcdWFjMDRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjE3Y1x1ZDU1OFx1YmE3MCBcdWM1NDRcdWM3NzhcdWMyODhcdWQwYzBcdWM3NzhcdWM3NTggXHVjMGMxXHViMzAwXHVjMTMxXHVjNzc0XHViODYwXHVjNzU4IFx1ZDYxNVx1YzEzMVx1YzVkMFx1YjNjNCBcdWFjZjVcdWQ1Y2NcdWQ1NWMgXHVhYzgzXHVjNzNjXHViODVjIFx1YzU0Y1x1YjgyNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUG9seWdvbiIsImRlc2NyaXB0aW9uIjoiPHA+QSBwb2x5Z29uIGNvbnNpc3RzIG9mIGFsbCBwb2ludHMgb24gb3IgZW5jbG9zZWQgYnkgaXRzIGJvcmRlci4gQSBjb252ZXggcG9seWdvbiBoYXMgdGhlIHByb3BlcnR5IHRoYXQgZm9yIGFueSB0d28gcG9pbnRzIFggYW5kIFkgb2YgdGhlIHBvbHlnb24sIHRoZSBsaW5lIHNlZ21lbnQgY29ubmVjdGluZyBYIGFuZCBZIGlzIGluc2lkZSB0aGUgcG9seWdvbi4gQWxsIHBvbHlnb25zIGluIHRoaXMgdGFzayBhcmUgY29udmV4IHBvbHlnb25zIHdpdGggYXQgbGVhc3QgdHdvIHZlcnRpY2VzLCBhbmQgYWxsIHZlcnRpY2VzIGluIGEgcG9seWdvbiBhcmUgZGlmZmVyZW50IGFuZCBoYXZlIGludGVnZXIgY29vcmRpbmF0ZXMuIE5vIHRocmVlIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIGFyZSBjb2xsaW5lYXIuIFRoZSB3b3JkICZxdW90O3BvbHlnb24mcXVvdDsgYmVsb3cgYWx3YXlzIHJlZmVycyB0byBzdWNoIHBvbHlnb25zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiB0d28gcG9seWdvbnMgQSBhbmQgQiwgdGhlIE1pbmtvd3NraSBzdW0gb2YgQSBhbmQgQiBjb25zaXN0cyBvZiBhbGwgdGhlIHBvaW50cyBvZiB0aGUgZm9ybSAoeDEreDIsIHkxK3kyKSB3aGVyZSAoeDEsIHkxKSBpcyBhIHBvaW50IGluIEEgYW5kICh4MiwgeTIpIGlzIGEgcG9pbnQgaW4gQi4gSXQgdHVybnMgb3V0IHRoYXQgdGhlIE1pbmtvd3NraSBzdW0gb2YgcG9seWdvbnMgaXMgYWxzbyBhIHBvbHlnb24uIFRoZSBmaWd1cmUgYmVsb3cgc2hvd3MgYW4gZXhhbXBsZTogdHdvIHRyaWFuZ2xlcyBhbmQgdGhlaXIgTWlua293c2tpIHN1bS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90YXNrMWEuanBnXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IHdpZHRoOjQ3OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldlIHN0dWR5IGEgcmV2ZXJzZSBvcGVyYXRpb24gdG8gdGhlIE1pbmtvd3NraSBzdW0uIEZvciBhIGdpdmVuIHBvbHlnb24gUCwgd2UgYXJlIGxvb2tpbmcgZm9yIHR3byBwb2x5Z29ucyBBIGFuZCBCIHN1Y2ggdGhhdDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5QIGlzIHRoZSBNaW5rb3dza2kgc3VtIG9mIEEgYW5kIEIsPFwvbGk+XHJcblx0PGxpPkEgaGFzIGZyb20gMiB0byA0IGRpZmZlcmVudCB2ZXJ0aWNlcywgaS5lLiBpdCBpcyBhIHNlZ21lbnQgKDIgdmVydGljZXMpLCBhIHRyaWFuZ2xlICgzIHZlcnRpY2VzKSBvciBhIHF1YWRyaWxhdGVyYWwgKDQgdmVydGljZXMpLDxcL2xpPlxyXG5cdDxsaT5BIHNob3VsZCBoYXZlIGFzIG1hbnkgdmVydGljZXMsIGFzIHBvc3NpYmxlLCBpLmUuOlxyXG5cdDx1bD5cclxuXHRcdDxsaT5BIHNob3VsZCBiZSBhIHF1YWRyaWxhdGVyYWwsIGlmIHBvc3NpYmxlLDxcL2xpPlxyXG5cdFx0PGxpPmlmIEEgY2Fubm90IGJlIGEgcXVhZHJpbGF0ZXJhbCwgaXQgc2hvdWxkIGJlIGEgdHJpYW5nbGUsIGlmIHBvc3NpYmxlLDxcL2xpPlxyXG5cdFx0PGxpPm90aGVyd2lzZSBpdCBzaG91bGQgYmUgYSBzZWdtZW50LjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkNsZWFybHksIG5laXRoZXIgQSBub3IgQiBjYW4gYmUgZXF1YWwgdG8gUCBiZWNhdXNlIHRoZW4gdGhlIG90aGVyIHN1bW1hbmQgd291bGQgaGF2ZSB0byBiZSBhIHBvaW50LCB3aGljaCBpcyBub3QgYSB2YWxpZCBwb2x5Z29uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIGEgc2V0IG9mIGlucHV0IGZpbGVzLCBlYWNoIGNvbnRhaW5pbmcgYSBkZXNjcmlwdGlvbiBvZiBhIHBvbHlnb24gUC4gRm9yIGVhY2ggaW5wdXQgZmlsZSB5b3Ugc2hvdWxkIGZpbmQgdGhlIHBvbHlnb25zIEEgYW5kIEIsIGFzIHJlcXVpcmVkIGFib3ZlLCBhbmQgY3JlYXRlIGFuIG91dHB1dCBmaWxlIGNvbnRhaW5pbmcgZGVzY3JpcHRpb25zIG9mIEEgYW5kIEIuIEZvciB0aGUgZ2l2ZW4gaW5wdXQgZmlsZXMgc3VjaCBwb2x5Z29ucyBBIGFuZCBCIGNhbiBhbHdheXMgYmUgZm91bmQuIElmIHRoZXJlIGFyZSBtYW55IGNvcnJlY3QgcmVzdWx0cywgeW91IHNob3VsZCBmaW5kIGFuZCBvdXRwdXQgb25lIG9mIHRoZW0uIFlvdSBzaG91bGQgbm90IHN1Ym1pdCBhbnkgcHJvZ3JhbXMsIGp1c3QgdGhlIG91dHB1dCBmaWxlcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdSBhcmUgZ2l2ZW4gMTAgcHJvYmxlbSBpbnN0YW5jZXMgaW4gdGhlIHRleHQgZmlsZXMgbmFtZWQgcG9seWdvbjEuaW4gdG8gcG9seWdvbjEwLmluLCB3aGVyZSB0aGUgbnVtYmVyIGFmdGVyIHBvbHlnb24gaXMgdGhlIGlucHV0IG51bWJlci4gRWFjaCBpbnB1dCBmaWxlIGlzIG9yZ2FuaXplZCBhcyBmb2xsb3dzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBOOiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIFAuIFRoZSBmb2xsb3dpbmcgTiBsaW5lcyBkZXNjcmliZSB0aGUgdmVydGljZXMgaW4gYSBjb3VudGVyLWNsb2Nrd2lzZSBvcmRlciwgb25lIHZlcnRleCBwZXIgbGluZS4gTGluZSBJKzEgKGZvciBJID0gMSwgMiwgLi4uLCBOKSBjb250YWlucyB0d28gaW50ZWdlcnMgWEkgYW5kIFlJLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZTogY29vcmRpbmF0ZXMgb2YgdGhlIEl0aCB2ZXJ0ZXggb2YgdGhlIHBvbHlnb24uIEFsbCBpbnB1dCBjb29yZGluYXRlcyBhcmUgbm9uLW5lZ2F0aXZlIGludGVnZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBhcmUgdG8gc3VibWl0IDEwIG91dHB1dCBmaWxlcyBjb3JyZXNwb25kaW5nIHRvIHRoZSBnaXZlbiBpbnB1dCBmaWxlcyB3aGljaCBkZXNjcmliZSB0aGUgcmVxdWlyZWQgcG9seWdvbnMgQSBhbmQgQi4gVGhlIGZpcnN0IGxpbmUgaXMgdG8gY29udGFpbiB0aGUgdGV4dDogI0ZJTEUgcG9seWdvbiBJIHdoZXJlIGludGVnZXIgSSAoMSZsZTsgSSAmbGU7MTApaXMgdGhlIG51bWJlciBvZiB0aGUgcmVzcGVjdGl2ZSBpbnB1dCBmaWxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgb3V0cHV0IGZvcm1hdCBpcyBzaW1pbGFyIHRvIHRoZSBpbnB1dCBmb3JtYXQuIFRoZSBzZWNvbmQgbGluZSBpcyB0byBjb250YWluIG9uZSBpbnRlZ2VyIE5BOiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIEEgKDIgJmxlO05BICZsZTs0KS4gVGhlIGZvbGxvd2luZyBOQSBsaW5lcyBkZXNjcmliZSB0aGUgdmVydGljZXMgb2YgQSBpbiB0aGUgY291bnRlci1jbG9ja3dpc2Ugb3JkZXIsIG9uZSB2ZXJ0ZXggcGVyIGxpbmUuIExpbmUgSSsyIChmb3IgSSA9IDEsIDIsIC4uLiwgTkEpIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBYIGFuZCBZLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZTogY29vcmRpbmF0ZXMgb2YgdGhlIEl0aCB2ZXJ0ZXggb2YgdGhlIHBvbHlnb24gQS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGluZSBOQSszIHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIE5COiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIEIsICgyICZsZTtOQikuIFRoZSBmb2xsb3dpbmcgTkIgbGluZXMgZGVzY3JpYmUgdGhlIHZlcnRpY2VzIG9mIEIgaW4gdGhlIGNvdW50ZXItY2xvY2t3aXNlIG9yZGVyLCBvbmUgdmVydGV4IHBlciBsaW5lLiBMaW5lIE5BK0orMyAoZm9yIEogPSAxLCAyLCAuLi4sIE5CKSBjb250YWlucyB0d28gaW50ZWdlcnMgWCBhbmQgWSwgc2VwYXJhdGVkIGJ5IGEgc3BhY2U6IGNvb3JkaW5hdGVzIG9mIHRoZSBKdGggdmVydGV4IG9mIHRoZSBwb2x5Z29uIEIuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > International Olympiad in Informatics > IOI 2004 3번

  • 잘못된 조건을 찾은 사람: doju
  • 잘못된 데이터를 찾은 사람: pjsdream