시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 787 350 244 42.288%

문제

현상금 사냥꾼인 정은이는 지금 범죄자를 쫓고 있는 중이다. 정은이는 갈치 II호를 사용해서 우주를 돌아다니면서 조사를 하는데, 2차원 유클리드 우주에 존재하는 N개의 다른 행성을 모두 방문한 다음 시작위치로 돌아와야 한다. 시작위치는 가장 왼쪽의 행성(with the lowest x-coordinate)이고, 정은이는 모든 행성을 방문해서 조사해야 한다. 하지만 가난하지만 사치스러운, 정은이는 돈을 아껴서 비싼 소고기를 먹기 위해서, 최소한의 거리로 행성을 모두 방문하기 원한다.

추가적으로 그는 CTP라는 범죄조직을 쫓고 있는데, 그들한테서 들키지 않도록, 정은이는 조사할때, x의 좌표가 오름차순인 순서대로 행성을 방문하고, 가장 오른쪽(with the largest x-coordinate)에 있는 행성을 방문하면, 다시 내림차순 순서대로 시작위치로 돌아와야 한다.

입력

입력은 테스트케이스 T (1 ≤ T ≤ 100)가 주어진다. 각각의 테스트 케이스는 여행에서 방문해야 할 장소의 수 N (2 ≤ N ≤ 512)과 각각의 좌표 (0 ≤ x, y ≤ 5000)가 주어진다. 입력으로 주어지는 x좌표는 중복되지 않으며, 증가하는 순서대로 주어진다. 모든 좌표는 정수이다.

출력

각각의 테스트케이스마다 여행의 최단거리를 출력한다. 오차는 최대 10-2까지 허용된다.

예제 입력 1

2
5
0 1
1 2
2 0
3 2
4 1
3
100 1
200 1
300 1

예제 출력 1

9.300563079746
400
W3sicHJvYmxlbV9pZCI6IjEwMjcyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNjA0XHVjMGMxXHVhZTA4IFx1YzBhY1x1YjBlNVx1YWZiYyBcdWFlNDBcdWM4MTVcdWM3NDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDYwNFx1YzBjMVx1YWUwOCBcdWMwYWNcdWIwZTVcdWFmYmNcdWM3NzggXHVjODE1XHVjNzQwXHVjNzc0XHViMjk0IFx1YzljMFx1YWUwOCBcdWJjOTRcdWM4YzRcdWM3OTBcdWI5N2MgXHVjYWQzXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM5MTFcdWM3NzRcdWIyZTQuIFx1YzgxNVx1Yzc0MFx1Yzc3NFx1YjI5NCBcdWFjMDhcdWNlNTggSUlcdWQ2MzhcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTc0XHVjMTFjIFx1YzZiMFx1YzhmY1x1Yjk3YyBcdWIzY2NcdWM1NDRcdWIyZTRcdWIyYzhcdWJhNzRcdWMxMWMgXHVjODcwXHVjMGFjXHViOTdjIFx1ZDU1OFx1YjI5NFx1YjM3MCwgMlx1Y2MyOFx1YzZkMCBcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVjNmIwXHVjOGZjXHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWQ1ODlcdWMxMzFcdWM3NDQgXHViYWE4XHViNDUwIFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWIyZTRcdWM3NGMgXHVjMmRjXHVjNzkxXHVjNzA0XHVjZTU4XHViODVjIFx1YjNjY1x1YzU0NFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzJkY1x1Yzc5MVx1YzcwNFx1Y2U1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNzU4IFx1ZDU4OVx1YzEzMSh3aXRoIHRoZSBsb3dlc3QgeC1jb29yZGluYXRlKVx1Yzc3NFx1YWNlMCwgXHVjODE1XHVjNzQwXHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWQ1ODlcdWMxMzFcdWM3NDQgXHViYzI5XHViYjM4XHVkNTc0XHVjMTFjIFx1Yzg3MFx1YzBhY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWFjMDBcdWIwOWNcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjMGFjXHVjZTU4XHVjMmE0XHViN2VjXHVjNmI0LCBcdWM4MTVcdWM3NDBcdWM3NzRcdWIyOTQgXHViM2M4XHVjNzQ0IFx1YzU0NFx1YWVmNFx1YzExYyBcdWJlNDRcdWMyZmMgXHVjMThjXHVhY2UwXHVhZTMwXHViOTdjIFx1YmEzOVx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCBcdWFjNzBcdWI5YWNcdWI4NWMgXHVkNTg5XHVjMTMxXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWJjMjlcdWJiMzhcdWQ1NThcdWFlMzAgXHVjNmQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkOTRcdWFjMDBcdWM4MDFcdWM3M2NcdWI4NWMgXHVhZGY4XHViMjk0IENUUFx1Yjc3Y1x1YjI5NCBcdWJjOTRcdWM4YzRcdWM4NzBcdWM5YzFcdWM3NDQgXHVjYWQzXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVhZGY4XHViNGU0XHVkNTVjXHVkMTRjXHVjMTFjIFx1YjRlNFx1ZDBhNFx1YzljMCBcdWM1NGFcdWIzYzRcdWI4NWQsIFx1YzgxNVx1Yzc0MFx1Yzc3NFx1YjI5NCBcdWM4NzBcdWMwYWNcdWQ1NjBcdWI1NGMsIHhcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1Yzc3OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTg5XHVjMTMxXHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCh3aXRoIHRoZSBsYXJnZXN0IHgtY29vcmRpbmF0ZSlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDU4OVx1YzEzMVx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWJhNzQsIFx1YjJlNFx1YzJkYyBcdWIwYjRcdWI5YmNcdWNjMjhcdWMyMWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzJkY1x1Yzc5MVx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2NDBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNCBUICgxICZsZTsgVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM1ZWNcdWQ1ODlcdWM1ZDBcdWMxMWMgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU2MCBcdWM3YTVcdWMxOGNcdWM3NTggXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgNTEyKVx1YWNmYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjODhjXHVkNDVjICgwICZsZTsgeCwgeSAmbGU7IDUwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCB4XHVjODhjXHVkNDVjXHViMjk0IFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzVlY1x1ZDU4OVx1Yzc1OCBcdWNkNWNcdWIyZThcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM2MjRcdWNjMjhcdWIyOTQgXHVjZDVjXHViMzAwIDEwPHN1cD4tMjxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwMjcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQm91bnR5IEh1bnRlciIsImRlc2NyaXB0aW9uIjoiPHA+U3Bpa2UgaXMgYSBib3VudHkgaHVudGVyIGFuZCBoZSBpcyBjdXJyZW50bHkgdHJhY2tpbmcgYSBjcmltaW5hbCEgVG8gaW52ZXN0aWdhdGUgaGUgdXNlcyBoaXMgc3BhY2VzaGlwLCB0aGUgU3dvcmRmaXNoIElJLCBhbmQgdHJhdmVscyB0byBOIGRpZmZlcmVudCBwbGFjZXMgb24gMkQgRXVjbGlkZWFuIHNwYWNlIGJlZm9yZSByZXR1cm5pbmcgdG8gaGlzIGNyZXcgYXQgdGhlIHN0YXJ0aW5nIGxvY2F0aW9uIHdpdGggYWxsIHRoZSBpbmZvcm1hdGlvbiBoZSBoYXMgZ2F0aGVyZWQuIFRoZSBzdGFydGluZyBsb2NhdGlvbiBpcyB0aGUgbGVmdG1vc3QgcGxhY2UgKHdpdGggdGhlIGxvd2VzdCB4LWNvb3JkaW5hdGUpIGFuZCBTcGlrZSB3YW50cyB0byB0cmF2ZWwgdG8gZXZlcnkgb3RoZXIgcGxhY2UgYmVmb3JlIHJldHVybmluZy4gSG93ZXZlciBzcGFjZSBmdWVsIGNvc3RzIGEgbG90IG9mIFdvb2xvbmdzIGFuZCBTcGlrZSB3b3VsZCByYXRoZXIgc3BlbmQgaGlzIG1vbmV5IG9uIHNwZWNpYWwgYmVlZiB3aXRoIGJlbGwgcGVwcGVycy4gVGhlcmVmb3JlIGhlIHdhbnRzIHRvIHRyYXZlbCB0aGUgbWluaW11bSBwb3NzaWJsZSBkaXN0YW5jZS48XC9wPlxyXG5cclxuPHA+T24gdG9wIG9mIHRoYXQgaGUgaXMgYmVpbmcgY2hhc2VkIGJ5IHRoZSBSZWQgRHJhZ29uIGNyaW1lIHN5bmRpY2F0ZS4gVG8gbWFrZSBzdXJlIHRoZXkgZG9uJnJzcXVvO3QgY2F0Y2ggaGltIGhlIGNhbiBvbmx5IHZpc2l0IHBsYWNlcyBpbiBpbmNyZWFzaW5nIG9yZGVyIG9mIHRoZWlyIHgtY29vcmRpbmF0ZSB1bnRpbCBoZSByZWFjaGVzIHRoZSByaWdodG1vc3QgcGxhY2UgKHdpdGggdGhlIGxhcmdlc3QgeC1jb29yZGluYXRlKSwgdGhlbiBoZSBjYW4gdHVybiBhcm91bmQgYW5kIHZpc2l0IHBsYWNlcyBpbiBkZWNyZWFzaW5nIG9yZGVyIG9mIHRoZWlyIHgtY29vcmRpbmF0ZSB1bnRpbCBoZSByZWFjaGVzIGhpcyBzdGFydGluZyBsb2NhdGlvbiBhZ2Fpbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIFQgKDEgJmxlOyBUICZsZTsgMTAwKSBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0aGF0IGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYW4gaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDUxMikgc3BlY2lmeWluZyB0aGUgbnVtYmVyIG9mIHBsYWNlcyBpbiB0aGUgdG91ci4gVGhlIGNvb3JkaW5hdGVzIG9mIHRoZXNlIHBsYWNlcyBhcmUgZ2l2ZW4gYXMgaW50ZWdlcnMgaW4gdGhlIG5leHQgTiBsaW5lcywgeC1jb29yZGluYXRlIGZpcnN0LCB5LWNvb3JkaW5hdGUgc2Vjb25kICgwICZsZTsgeCwgeSAmbGU7IDUwMDApLiBUaGUgcGxhY2VzIGFyZSBnaXZlbiBpbiBhc2NlbmRpbmcgb3JkZXIgb2YgdGhlIHgtY29vcmRpbmF0ZS4gRXZlcnkgcGxhY2UgaGFzIGEgdW5pcXVlIHgtY29vcmRpbmF0ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBvbiBhIHNpbmdsZSBsaW5lIHRoZSBtaW5pbXVtIHRyYXZlbCBkaXN0YW5jZSBuZWVkZWQgdG8gY29tcGxldGUgdGhlIHRvdXIuIFlvdXIgb3V0cHV0IHNob3VsZCBoYXZlIGFuIGFic29sdXRlIG9yIHJlbGF0aXZlIGVycm9yIG9mIGF0IG1vc3QgMTA8c3VwPi0yPFwvc3VwPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2014 C번