시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 128 MB32266.667%

문제

어떤 도시의 도로 지도가 주어졌을 때, 주어진 두 점 사이의 최단거리를 찾는 프로그램을 작성하시오.

도로 지도는 평면 위의 선분의 집합으로 표현한다.

위의 그림은 도로 지도의 예이다. 어떤 선분은 도로를 나타내고, 나머지 선분은 어떤 방향으로 움직일 수 없는지를 나타내는 표지판이다. 위의 그림에서는 AE, AM, MQ, EQ, CP, HJ는 도로를 나타내고, 나머지는 표지판을 나타낸다. 어떤 선분의 양 끝점 중, 한 끝점은 선분과 만나고, 다른 끝점은 그렇지 않다면, 그 선분은 표지판을 나타내는 선분이다.

그림에서 표지판 BF는 점 B에서 차는 왼쪽에서 오른쪽으로 움직일 수 있지만, 반대방향으로는 움직일 수 없다는 뜻이다. 표지판과 도로가 이루는 각 중, 둔각이 있는 방향에서 예각쪽으로는 이동할 수 없다. (각 CBF는 둔각이고, ABF는 예각이다) 따라서, 위의 지도에서 P에서 M으로 가거나, M에서 P로는 갈 수가 없다. 만약, 표지판과 도로가 직각을 이루는 경우에는 그 표지판을 지날 수 없다는 뜻이다. 위의 그림에서는 IL때문에, H에서 J로, J에서 H로 갈 수가 없다.

두 점이 주어졌을 때, 위의 규칙을 지키면서 가장 짧은 경로를 찾는 프로그램을 작성하시오. 두 점 (x1, y1), (x2, y2)사이의 거리는 루트((x2-x1)2+(y2-y1)2)와 같다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어 있다.

테스트 케이스의 첫째 줄에는 선분의 개수 n이 주어진다. n은 200보다 작거나 같은 자연수이다. 둘째 줄에는 xs와 ys가, 셋째 줄에는 xg와 yg가 우어진다. (xs,sy)는 시작점, (xg,yg)는 끝점이고, 두 점 사이의 최단 거리를 계산하면 된다. (xs,ys)는 (xg,yg)는 같지 않으며, 최단 경로는 항상 유일하다.

다음 줄부터 n개의 줄에는 선분의 정보가 주어진다. 선분의 정보는 x1k y1k x2k y2k와 같은 형식으로 주어지며, k번째 선분의 양 끝점이다. (x1k,y1k)와 (x2k,y2k)는 같지 않고, 두 선분이 교차하는 경우는 없다. 즉, 선분은 항상 끝점을 공유한다.

모든 좌표는 1000보다 작거나 같은 음이 아닌 정수이다.

출력

각각의 테스트 케이스에 대해서, 입력으로 주어진 시작점과 끝점사이의 최단 경로 중 교차점을 모두 출력한다. 각 테스트 케이스의 마지막 줄에는 0을 출력한다.

교차점은 적어도 두 선분이 만나는 점을 말하며, x좌표와 y좌표를 공백으로 구분해서 출력한다. 만약 시작점에서 끝점으로 가는 경로가 없을 때는 -1을 출력한다.

예제 입력 1

3
8
1 1
4 4
1 1 4 1
1 1 1 4
3 1 3 4
4 3 5 3
2 4 3 5
4 1 4 4
3 3 2 2
1 4 4 4
9
1 5
5 1
5 4 5 1
1 5 1 1
1 5 5 1
2 3 2 4
5 4 1 5
3 2 2 1
4 2 4 1
1 1 5 1
5 3 4 3
11
5 5
1 0
3 1 5 1
4 3 4 2
3 1 5 5
2 3 2 2
1 0 1 2
1 2 3 4
3 4 5 5
1 0 5 2
4 0 4 1
5 5 5 1
2 3 2 4

예제 출력 1

1 1
3 1
3 4
4 4
0
-1
5 5
5 2
3 1
1 0
0
W3sicHJvYmxlbV9pZCI6IjM4OTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWMgXHVjOWMwXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM1YjRcdWI1YTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YjNjNFx1Yjg1YyBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjQ1MCBcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViM2M0XHViODVjIFx1YzljMFx1YjNjNFx1YjI5NCBcdWQzYzlcdWJhNzQgXHVjNzA0XHVjNzU4IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3JvYWQucG5nXCIgc3R5bGU9XCJ3aWR0aDogNTQzcHg7IGhlaWdodDogMjk1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViM2M0XHViODVjIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWM2MDhcdWM3NzRcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWMxMjBcdWJkODRcdWM3NDAgXHViM2M0XHViODVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWM1YjRcdWI1YTQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNWM2XHViMjk0XHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWQ0NWNcdWM5YzBcdWQzMTBcdWM3NzRcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWNcdWIyOTQgQUUsIEFNLCBNUSwgRVEsIENQLCBISlx1YjI5NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzBcdWIyOTQgXHVkNDVjXHVjOWMwXHVkMzEwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjODEwIFx1YzkxMSwgXHVkNTVjIFx1YjA1ZFx1YzgxMFx1Yzc0MCBcdWMxMjBcdWJkODRcdWFjZmMgXHViOWNjXHViMDk4XHVhY2UwLCBcdWIyZTRcdWI5NzggXHViMDVkXHVjODEwXHVjNzQwIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWMxMjBcdWJkODRcdWM3NDAgXHVkNDVjXHVjOWMwXHVkMzEwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWQ0NWNcdWM5YzBcdWQzMTAgQkZcdWIyOTQgXHVjODEwIEJcdWM1ZDBcdWMxMWMgXHVjYzI4XHViMjk0IFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1YmMxOFx1YjMwMFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1Y1x1YjI5NCBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIFx1ZDQ1Y1x1YzljMFx1ZDMxMFx1YWNmYyBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNzc0XHViOGU4XHViMjk0IFx1YWMwMSBcdWM5MTEsIFx1YjQ1NFx1YWMwMVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHViYzI5XHVkNWE1XHVjNWQwXHVjMTFjIFx1YzYwOFx1YWMwMVx1Y2FiZFx1YzczY1x1Yjg1Y1x1YjI5NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gKFx1YWMwMSBDQkZcdWIyOTQgXHViNDU0XHVhYzAxXHVjNzc0XHVhY2UwLCBBQkZcdWIyOTQgXHVjNjA4XHVhYzAxXHVjNzc0XHViMmU0KSBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzcwNFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWM1ZDBcdWMxMWMgUFx1YzVkMFx1YzExYyBNXHVjNzNjXHViODVjIFx1YWMwMFx1YWM3MFx1YjA5OCwgTVx1YzVkMFx1YzExYyBQXHViODVjXHViMjk0IFx1YWMwOCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1ZDQ1Y1x1YzljMFx1ZDMxMFx1YWNmYyBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjOWMxXHVhYzAxXHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1ZDQ1Y1x1YzljMFx1ZDMxMFx1Yzc0NCBcdWM5YzBcdWIwYTAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWNcdWIyOTQgSUxcdWI1NGNcdWJiMzhcdWM1ZDAsIEhcdWM1ZDBcdWMxMWMgSlx1Yjg1YywgSlx1YzVkMFx1YzExYyBIXHViODVjIFx1YWMwOCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHVjODEwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhY2JkXHViODVjXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI0NTAgXHVjODEwICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pLCAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KVx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHViOGU4XHVkMmI4KCh4PHN1Yj4yPFwvc3ViPi14PHN1Yj4xPFwvc3ViPik8c3VwPjI8XC9zdXA+Kyh5PHN1Yj4yPFwvc3ViPi15PHN1Yj4xPFwvc3ViPik8c3VwPjI8XC9zdXA+KVx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIDIwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCB4PHN1Yj5zPFwvc3ViPlx1YzY0MCB5PHN1Yj5zPFwvc3ViPlx1YWMwMCwgXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCB4PHN1Yj5nPFwvc3ViPlx1YzY0MCB5PHN1Yj5nPFwvc3ViPlx1YWMwMCBcdWM2YjBcdWM1YjRcdWM5YzRcdWIyZTQuICh4PHN1Yj5zPFwvc3ViPixzPHN1Yj55PFwvc3ViPilcdWIyOTQgXHVjMmRjXHVjNzkxXHVjODEwLCAoeDxzdWI+ZzxcL3N1Yj4seTxzdWI+ZzxcL3N1Yj4pXHViMjk0IFx1YjA1ZFx1YzgxMFx1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YzgxMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjZDVjXHViMmU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiAoeDxzdWI+czxcL3N1Yj4seTxzdWI+czxcL3N1Yj4pXHViMjk0ICh4PHN1Yj5nPFwvc3ViPix5PHN1Yj5nPFwvc3ViPilcdWIyOTQgXHVhYzE5XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxMjBcdWJkODRcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IHg8c3ViPjE8XC9zdWI+PHN1cD5rPFwvc3VwPiB5PHN1Yj4xPFwvc3ViPjxzdXA+azxcL3N1cD4geDxzdWI+MjxcL3N1Yj48c3VwPms8XC9zdXA+IHk8c3ViPjI8XC9zdWI+PHN1cD5rPFwvc3VwPlx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwga1x1YmM4OFx1YzlmOCBcdWMxMjBcdWJkODRcdWM3NTggXHVjNTkxIFx1YjA1ZFx1YzgxMFx1Yzc3NFx1YjJlNC4gKHg8c3ViPjE8XC9zdWI+PHN1cD5rPFwvc3VwPix5PHN1Yj4xPFwvc3ViPjxzdXA+azxcL3N1cD4pXHVjNjQwICh4PHN1Yj4yPFwvc3ViPjxzdXA+azxcL3N1cD4seTxzdWI+MjxcL3N1Yj48c3VwPms8XC9zdXA+KVx1YjI5NCBcdWFjMTlcdWM5YzAgXHVjNTRhXHVhY2UwLCBcdWI0NTAgXHVjMTIwXHViZDg0XHVjNzc0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM5ODksIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViMDVkXHVjODEwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAxMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzJkY1x1Yzc5MVx1YzgxMFx1YWNmYyBcdWIwNWRcdWM4MTBcdWMwYWNcdWM3NzRcdWM3NTggXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1YyBcdWM5MTEgXHVhZDUwXHVjYzI4XHVjODEwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWQ1MFx1Y2MyOFx1YzgxMFx1Yzc0MCBcdWM4MDFcdWM1YjRcdWIzYzQgXHViNDUwIFx1YzEyMFx1YmQ4NFx1Yzc3NCBcdWI5Y2NcdWIwOThcdWIyOTQgXHVjODEwXHVjNzQ0IFx1YjlkMFx1ZDU1OFx1YmE3MCwgeFx1Yzg4Y1x1ZDQ1Y1x1YzY0MCB5XHVjODhjXHVkNDVjXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjMmRjXHVjNzkxXHVjODEwXHVjNWQwXHVjMTFjIFx1YjA1ZFx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWIyOTQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM4OTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHZW9tZXRyaWMgTWFwIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3VyIHRhc2sgaW4gdGhpcyBwcm9ibGVtIGlzIHRvIGNyZWF0ZSBhIHByb2dyYW0gdGhhdCBcdWZiMDFuZHN0aGUgc2hvcnRlc3QgcGF0aCBiZXR3ZWVuIHR3byBnaXZlbiBsb2NhdGlvbnMgb24gYSBnaXZlbiBzdHJlZXQgbWFwLCB3aGljaCBpcyByZXByZXNlbnRlZCBhcyBhIGNvbGxlY3Rpb24gb2YgbGluZSBzZWdtZW50cyBvbiBhIHBsYW5lLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2dlb21hcC5wbmdcIiBzdHlsZT1cImhlaWdodDozMzZweDsgd2lkdGg6NTgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDQgaXMgYW4gZXhhbXBsZSBvZiBhIHN0cmVldCBtYXAsIHdoZXJlIHNvbWUgbGluZSBzZWdtZW50cyByZXByZXNlbnQgc3RyZWV0cyBhbmQgdGhlIG90aGVycyBhcmUgc2lnbnMgaW5kaWNhdGluZyB0aGUgZGlyZWN0aW9ucyBpbiB3aGljaCBjYXJzIGNhbm5vdCBtb3ZlLiBNb3JlIGNvbmNyZXRlbHksIEFFLCBBTSwgTVEsIEVRLCBDUCBhbmQgSEogcmVwcmVzZW50IHRoZSBzdHJlZXRzIGFuZCB0aGUgb3RoZXJzIGFyZSBzaWducyBpbiB0aGlzIG1hcC4gSW4gZ2VuZXJhbCwgYW4gZW5kIHBvaW50IG9mIGEgc2lnbiB0b3VjaGVzIG9uZSBhbmQgb25seSBvbmUgbGluZSBzZWdtZW50IHJlcHJlc2VudGluZyBhIHN0cmVldCBhbmQgdGhlIG90aGVyIGVuZCBwb2ludCBpcyBvcGVuLiBFYWNoIGVuZCBwb2ludCBvZiBldmVyeSBzdHJlZXQgdG91Y2hlcyBvbmUgb3IgbW9yZSBzdHJlZXRzLCBidXQgbm8gc2lnbnMuPFwvcD5cclxuXHJcbjxwPlRoZSBzaWduIEJGLCBmb3IgaW5zdGFuY2UsIGluZGljYXRlcyB0aGF0IGF0IEIgY2FycyBtYXkgbW92ZSBsZWZ0IHRvIHJpZ2h0IGJ1dCBtYXkgbm90IGluIHRoZSByZXZlcnNlIGRpcmVjdGlvbi4gSW4gZ2VuZXJhbCwgY2FycyBtYXkgbm90IG1vdmUgZnJvbSB0aGUgb2J0dXNlIGFuZ2xlIHNpZGUgdG8gdGhlIGFjdXRlIGFuZ2xlIHNpZGUgYXQgYSBwb2ludCB3aGVyZSBhIHNpZ24gdG91Y2hlcyBhIHN0cmVldCAobm90ZSB0aGF0IHRoZSBhbmdsZSBDQkYgaXMgb2J0dXNlIGFuZCB0aGUgYW5nbGUgQUJGIGlzIGFjdXRlKS4gQ2FycyBtYXkgZGlyZWN0bHkgbW92ZSBuZWl0aGVyIGZyb20gUCB0byBNIG5vciBmcm9tIE0gdG8gUCBzaW5jZSBjYXJzIG1vdmluZyBsZWZ0IHRvIHJpZ2h0IG1heSBub3QgZ28gdGhyb3VnaCBOIGFuZCB0aG9zZSBtb3ZpbmcgcmlnaHQgdG8gbGVmdCBtYXkgbm90IGdvIHRocm91Z2ggTy4gSW4gYSBzcGVjaWFsIGNhc2Ugd2hlcmUgdGhlIGFuZ2xlIGJldHdlZW4gYSBzaWduIGFuZCBhIHN0cmVldCBpcyByZWN0YW5ndWxhciwgY2FycyBtYXkgbm90IG1vdmUgaW4gZWl0aGVyIGRpcmVjdGlvbnMgYXQgdGhlIHBvaW50LiBGb3IgaW5zdGFuY2UsIGNhcnMgbWF5IGRpcmVjdGx5IG1vdmUgbmVpdGhlciBmcm9tIEggdG8gSiBub3IgZnJvbSBKIHRvIEguPFwvcD5cclxuXHJcbjxwPllvdSBzaG91bGQgd3JpdGUgYSBwcm9ncmFtIHRoYXQgXHVmYjAxbmRzIHRoZSBzaG9ydGVzdCBwYXRoIG9iZXlpbmcgdGhlc2UgdHJhXHVmYjAzYyBydWxlcy4gVGhlIGxlbmd0aCBvZiBhIGxpbmUgc2VnbWVudCBiZXR3ZWVuJm5ic3A7KHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPikgYW5kICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4pIGlzJm5ic3A7c3FydCgoeDxzdWI+MjxcL3N1Yj4teDxzdWI+MTxcL3N1Yj4pPHN1cD4yPFwvc3VwPisoeTxzdWI+MjxcL3N1Yj4teTxzdWI+MTxcL3N1Yj4pPHN1cD4yPFwvc3VwPik8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSBkYXRhc2V0cywgZWFjaCBpbiB0aGUgZm9sbG93aW5nIGZvcm1hdC48XC9wPlxyXG5cclxuPHByZT5cclxublxyXG54PHN1Yj5zPFwvc3ViPiB5PHN1Yj5zPFwvc3ViPlxyXG54PHN1Yj5nPFwvc3ViPiB5PHN1Yj5nPFwvc3ViPlxyXG54PHN1Yj4xPFwvc3ViPjxzdXA+MTxcL3N1cD4geTxzdWI+MTxcL3N1Yj48c3VwPjE8XC9zdXA+IHg8c3ViPjI8XC9zdWI+PHN1cD4xPFwvc3VwPiB5PHN1Yj4yPFwvc3ViPjxzdXA+MTxcL3N1cD5cclxuLi4uXHJcbng8c3ViPjE8XC9zdWI+PHN1cD5rPFwvc3VwPiB5PHN1Yj4xPFwvc3ViPjxzdXA+azxcL3N1cD4geDxzdWI+MjxcL3N1Yj48c3VwPms8XC9zdXA+IHk8c3ViPjI8XC9zdWI+PHN1cD5rPFwvc3VwPlxyXG4uLi5cclxueDxzdWI+MTxcL3N1Yj48c3VwPm48XC9zdXA+IHk8c3ViPjE8XC9zdWI+PHN1cD5uPFwvc3VwPiB4PHN1Yj4yPFwvc3ViPjxzdXA+bjxcL3N1cD4geTxzdWI+MjxcL3N1Yj48c3VwPm48XC9zdXA+PFwvcHJlPlxyXG5cclxuPHA+biwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgbGluZSBzZWdtZW50cywgaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiBvciBlcXVhbCB0byAyMDAuPFwvcD5cclxuXHJcbjxwPih4PHN1Yj5zPFwvc3ViPix5PHN1Yj5zPFwvc3ViPikgYW5kICh4PHN1Yj5nPFwvc3ViPix5PHN1Yj5nPFwvc3ViPikgYXJlIHRoZSBzdGFydCBhbmQgZ29hbCBwb2ludHMsIHJlc3BlY3RpdmVseS4gWW91IGNhbiBhc3N1bWUgdGhhdCAoeDxzdWI+czxcL3N1Yj4seTxzdWI+czxcL3N1Yj4pICZuZTsgKHg8cz5nPFwvcz4seTxzPmc8XC9zPikgYW5kIHRoYXQgZWFjaCBvZiB0aGVtIGlzIGxvY2F0ZWQgb24gYW4gZW5kIHBvaW50IG9mIHNvbWUgbGluZSBzZWdtZW50IHJlcHJlc2VudGluZyBhIHN0cmVldC4gWW91IGNhbiBhbHNvIGFzc3VtZSB0aGF0IHRoZSBzaG9ydGVzdCBwYXRoIGZyb20gKHg8c3ViPnM8XC9zdWI+LHk8c3ViPnM8XC9zdWI+KSB0byAoeDxzdWI+ZzxcL3N1Yj4seTxzdWI+ZzxcL3N1Yj4pIGlzIHVuaXF1ZTxcL3A+XHJcblxyXG48cD4oeDxzdWI+azxcL3N1Yj48c3VwPjE8XC9zdXA+LHk8c3ViPms8XC9zdWI+PHN1cD4xPFwvc3VwPikgYW5kICh4PHN1Yj5rPFwvc3ViPjxzdXA+MjxcL3N1cD4seTxzdWI+azxcL3N1Yj48c3VwPjI8XC9zdXA+KSBhcmUgdGhlIHR3byBlbmQgcG9pbnRzIG9mIHRoZSBrdGggbGluZSBzZWdtZW50LiBZb3UgY2FuIGFzc3VtZSB0aGF0ICh4PHN1Yj5rPFwvc3ViPjxzdXA+MTxcL3N1cD4seTxzdWI+azxcL3N1Yj48c3VwPjE8XC9zdXA+KSAmbmU7ICh4PHN1Yj5rPFwvc3ViPjxzdXA+MjxcL3N1cD4seTxzdWI+azxcL3N1Yj48c3VwPjI8XC9zdXA+KS4gVHdvIGxpbmUgc2VnbWVudHMgbmV2ZXIgY3Jvc3Mgbm9yIG92ZXJsYXAuIFRoYXQgaXMsIGlmIHRoZXkgc2hhcmUgYSBwb2ludCwgaXQgaXMgYWx3YXlzIG9uZSBvZiB0aGVpciBlbmQgcG9pbnRzLjxcL3A+XHJcblxyXG48cD5BbGwgdGhlIGNvb3JkaW5hdGVzIGFyZSBub24tbmVnYXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEwMDAuIFRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSB6ZXJvLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IGRhdGFzZXQsIHByaW50IGV2ZXJ5IHN0cmVldCBpbnRlcnNlY3Rpb24gcG9pbnQgb24gdGhlIHNob3J0ZXN0IHBhdGggZnJvbSB0aGUgc3RhcnQgcG9pbnQgdG8gdGhlIGdvYWwgcG9pbnQsIG9uZSBpbiBhbiBvdXRwdXQgbGluZSBpbiB0aGlzIG9yZGVyLCBhbmQgYSB6ZXJvIGluIGEgbGluZSBmb2xsb3dpbmcgdGhvc2UgcG9pbnRzLiBOb3RlIHRoYXQgYSBzdHJlZXQgaW50ZXJzZWN0aW9uIHBvaW50IGlzIGEgcG9pbnQgd2hlcmUgYXQgbGVhc3QgdHdvIGxpbmUgc2VnbWVudHMgcmVwcmVzZW50aW5nIHN0cmVldHMgbWVldC4gQW4gb3V0cHV0IGxpbmUgZm9yIGEgc3RyZWV0IGludGVyc2VjdGlvbiBwb2ludCBzaG91bGQgY29udGFpbiBpdHMgeGFuZCB5LWNvb3JkaW5hdGVzIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcblxyXG48cD5QcmludCAmbWludXM7MSBpZiB0aGVyZSBhcmUgbm8gcGF0aHMgZnJvbSB0aGUgc3RhcnQgcG9pbnQgdG8gdGhlIGdvYWwgcG9pbnQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2007 in Tokyo E번