시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 345 156 112 41.481%

문제

현상금 사냥꾼인 정은이는 지금 범죄자를 쫓고 있는 중이다. 정은이는 갈치 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+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNCBUICgxICZsZTsgVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM1ZWNcdWQ1ODlcdWM1ZDBcdWMxMWMgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU2MCBcdWM3YTVcdWMxOGNcdWM3NTggXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgNTEyKVx1YWNmYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjODhjXHVkNDVjICgwICZsZTsgeCwgeSAmbGU7IDUwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCB4XHVjODhjXHVkNDVjXHViMjk0IFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNWVjXHVkNTg5XHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1Y2MyOFx1YjI5NCBcdWNkNWNcdWIzMDAgMTA8c3VwPi0yPFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAyNzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCb3VudHkgSHVudGVyIiwiZGVzY3JpcHRpb24iOiI8cD5TcGlrZSBpcyBhIGJvdW50eSBodW50ZXIgYW5kIGhlIGlzIGN1cnJlbnRseSB0cmFja2luZyBhIGNyaW1pbmFsISBUbyBpbnZlc3RpZ2F0ZSBoZSB1c2VzIGhpcyBzcGFjZXNoaXAsIHRoZSBTd29yZGZpc2ggSUksIGFuZCB0cmF2ZWxzIHRvIE4gZGlmZmVyZW50IHBsYWNlcyBvbiAyRCBFdWNsaWRlYW4gc3BhY2UgYmVmb3JlIHJldHVybmluZyB0byBoaXMgY3JldyBhdCB0aGUgc3RhcnRpbmcgbG9jYXRpb24gd2l0aCBhbGwgdGhlIGluZm9ybWF0aW9uIGhlIGhhcyBnYXRoZXJlZC4gVGhlIHN0YXJ0aW5nIGxvY2F0aW9uIGlzIHRoZSBsZWZ0bW9zdCBwbGFjZSAod2l0aCB0aGUgbG93ZXN0IHgtY29vcmRpbmF0ZSkgYW5kIFNwaWtlIHdhbnRzIHRvIHRyYXZlbCB0byBldmVyeSBvdGhlciBwbGFjZSBiZWZvcmUgcmV0dXJuaW5nLiBIb3dldmVyIHNwYWNlIGZ1ZWwgY29zdHMgYSBsb3Qgb2YgV29vbG9uZ3MgYW5kIFNwaWtlIHdvdWxkIHJhdGhlciBzcGVuZCBoaXMgbW9uZXkgb24gc3BlY2lhbCBiZWVmIHdpdGggYmVsbCBwZXBwZXJzLiBUaGVyZWZvcmUgaGUgd2FudHMgdG8gdHJhdmVsIHRoZSBtaW5pbXVtIHBvc3NpYmxlIGRpc3RhbmNlLjxcL3A+XHJcblxyXG48cD5PbiB0b3Agb2YgdGhhdCBoZSBpcyBiZWluZyBjaGFzZWQgYnkgdGhlIFJlZCBEcmFnb24gY3JpbWUgc3luZGljYXRlLiBUbyBtYWtlIHN1cmUgdGhleSBkb24mcnNxdW87dCBjYXRjaCBoaW0gaGUgY2FuIG9ubHkgdmlzaXQgcGxhY2VzIGluIGluY3JlYXNpbmcgb3JkZXIgb2YgdGhlaXIgeC1jb29yZGluYXRlIHVudGlsIGhlIHJlYWNoZXMgdGhlIHJpZ2h0bW9zdCBwbGFjZSAod2l0aCB0aGUgbGFyZ2VzdCB4LWNvb3JkaW5hdGUpLCB0aGVuIGhlIGNhbiB0dXJuIGFyb3VuZCBhbmQgdmlzaXQgcGxhY2VzIGluIGRlY3JlYXNpbmcgb3JkZXIgb2YgdGhlaXIgeC1jb29yZGluYXRlIHVudGlsIGhlIHJlYWNoZXMgaGlzIHN0YXJ0aW5nIGxvY2F0aW9uIGFnYWluLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgVCAoMSAmbGU7IFQgJmxlOyAxMDApIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRoYXQgZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhbiBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgNTEyKSBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgcGxhY2VzIGluIHRoZSB0b3VyLiBUaGUgY29vcmRpbmF0ZXMgb2YgdGhlc2UgcGxhY2VzIGFyZSBnaXZlbiBhcyBpbnRlZ2VycyBpbiB0aGUgbmV4dCBOIGxpbmVzLCB4LWNvb3JkaW5hdGUgZmlyc3QsIHktY29vcmRpbmF0ZSBzZWNvbmQgKDAgJmxlOyB4LCB5ICZsZTsgNTAwMCkuIFRoZSBwbGFjZXMgYXJlIGdpdmVuIGluIGFzY2VuZGluZyBvcmRlciBvZiB0aGUgeC1jb29yZGluYXRlLiBFdmVyeSBwbGFjZSBoYXMgYSB1bmlxdWUgeC1jb29yZGluYXRlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uIGEgc2luZ2xlIGxpbmUgdGhlIG1pbmltdW0gdHJhdmVsIGRpc3RhbmNlIG5lZWRlZCB0byBjb21wbGV0ZSB0aGUgdG91ci4gWW91ciBvdXRwdXQgc2hvdWxkIGhhdmUgYW4gYWJzb2x1dGUgb3IgcmVsYXRpdmUgZXJyb3Igb2YgYXQgbW9zdCAxMDxzdXA+LTI8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==