시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 3 1 1 100.000%

문제

현우는 삼각형 모양의 그림을 두 점 갖고 있다. 두 번째 그림은 회전과 확대를 통해서 첫 번째 그림으로 바뀔 수 있다. 현우는 이 두 그림을 책상 위에 올려 놓았는데, 두 번째 그림은 첫 번째 그림의 완전한 내부에 있었다(경계에 닿을 수는 있다). 두 번째 그림은 정확히 0에서 1 사이의 확대율을 갖는다.

당신은 현우를 도와 두 그림의 어떤 지점이 정확히 겹쳐 있는지를  여러 개의 테스트케이스에 대해 찾아야 한다. 만약 그러한 지점이 한 개 이상 있다면, 어느 점을 찾아도 상관 없다. 만약 그러한 지점이 없다면, 그 테스트케이스에 대해서는 "No Solution"(""없이)을 출력한다.

입력

첫 번째 줄에는 테스트케이스의 수 N이 주어진다. 각각의 테스트케이스는 두 줄로 이루어져 있는데, 각 줄은 공백으로 분리된 6개의 정수로 주어진다. 각 줄은 x1 y1 x2 y2 x3 y3의 형태를 띄고 있으며, 첫 번째 그림의 첫 번째 꼭짓점(x1, y1)은 두 번째 그림의 첫 번째 꼭짓점 (x1, y1)와 정확히 대응된다. 이것은 두 번째 꼭짓점과 세 번째 꼭짓점에도 똑같이 적용된다.

1<=N<=10

각 점의 좌표는 -10000이상 10000이하이다. 삼각형의 세 점은 한 직선 위에 있지 않다는 것이 보장된다.

삼각형은 어느 모양이나 가질 수 있다.

출력

각각의 테스트케이스에 대해  "Case #x: "로 시작하는 한 줄의 출력을 작성한다. "Case #x: "뒤에는 두 그림이 겹쳐져 있는 지점 중 아무 점이나 좌표를 출력하거나 "No Solution"을 출력한다. 답과 0.00001의 상대오차나 절대오차는 고려하지 않는다.

예제 입력 1

2
0 0 0 2 2 0
0 0 0 1 1 0
10 0 0 10 0 0
3 3 1 1 3 1

예제 출력 1

Case #1: 0.000000 0.000000
Case #2: 2.692308 1.538462
W3sicHJvYmxlbV9pZCI6IjEyNjcyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGJjXHVhYzAxXHVkNjE1IFx1YmNjMFx1ZDY1OCAoTGFyZ2UpIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWM2YjBcdWIyOTQgXHVjMGJjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDQgXHViNDUwIFx1YzgxMCBcdWFjMTZcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWQ2OGNcdWM4MDRcdWFjZmMgXHVkNjU1XHViMzAwXHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWRmOFx1YjliY1x1YzczY1x1Yjg1YyBcdWJjMTRcdWIwMTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNjA0XHVjNmIwXHViMjk0IFx1Yzc3NCBcdWI0NTAgXHVhZGY4XHViOWJjXHVjNzQ0IFx1Y2M0NVx1YzBjMSBcdWM3MDRcdWM1ZDAgXHVjNjJjXHViODI0IFx1YjE5M1x1YzU1OFx1YjI5NFx1YjM3MCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFkZjhcdWI5YmNcdWM3NTggXHVjNjQ0XHVjODA0XHVkNTVjIFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWM1YzhcdWIyZTQoXHVhY2JkXHVhY2M0XHVjNWQwIFx1YjJmZlx1Yzc0NCBcdWMyMThcdWIyOTQgXHVjNzg4XHViMmU0KS4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjODE1XHVkNjU1XHVkNzg4IDBcdWM1ZDBcdWMxMWMgMSBcdWMwYWNcdWM3NzRcdWM3NTggXHVkNjU1XHViMzAwXHVjNzI4XHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1ZDYwNFx1YzZiMFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHViNDUwIFx1YWRmOFx1YjliY1x1Yzc1OCBcdWM1YjRcdWI1YTQgXHVjOWMwXHVjODEwXHVjNzc0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWFjYjlcdWNjZDAgXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjICZuYnNwO1x1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCZuYnNwO1x1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjOWMwXHVjODEwXHVjNzc0IFx1ZDU1YyBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjNWI0XHViMjkwIFx1YzgxMFx1Yzc0NCBcdWNjM2VcdWM1NDRcdWIzYzQgXHVjMGMxXHVhZDAwIFx1YzVjNlx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM5YzBcdWM4MTBcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0LCBcdWFkZjggXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCAmcXVvdDtObyBTb2x1dGlvbiZxdW90OygmcXVvdDsmcXVvdDtcdWM1YzZcdWM3NzQpXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MWMgNlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwJm5ic3A7eDEmbmJzcDt5MSZuYnNwO3gyJm5ic3A7eTImbmJzcDt4MyZuYnNwO3kzXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjk3YyBcdWI3NDRcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWRmOFx1YjliY1x1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWYyZFx1YzlkM1x1YzgxMCh4MSwgeTEpXHVjNzQwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVhZGY4XHViOWJjXHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZjJkXHVjOWQzXHVjODEwICh4MSwgeTEpXHVjNjQwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWIzMDBcdWM3NTFcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YWM4M1x1Yzc0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWYyZFx1YzlkM1x1YzgxMFx1YWNmYyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YWYyZFx1YzlkM1x1YzgxMFx1YzVkMFx1YjNjNCBcdWI2MTFcdWFjMTlcdWM3NzQgXHVjODAxXHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xJmx0Oz1OJmx0Oz0xMDxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAtMTAwMDBcdWM3NzRcdWMwYzEgMTAwMDBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWMxMzggXHVjODEwXHVjNzQwIFx1ZDU1YyBcdWM5YzFcdWMxMjAgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YzViNFx1YjI5MCBcdWJhYThcdWM1OTFcdWM3NzRcdWIwOTggXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgJm5ic3A7JnF1b3Q7Q2FzZSAjeDogJnF1b3Q7XHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNzU4IFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NWNcdWIyZTQuICZxdW90O0Nhc2UgI3g6ICZxdW90O1x1YjRhNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVhZGY4XHViOWJjXHVjNzc0IFx1YWNiOVx1Y2NkMFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVjOWMwXHVjODEwIFx1YzkxMSBcdWM1NDRcdWJiMzQgXHVjODEwXHVjNzc0XHViMDk4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjNzBcdWIwOTggJnF1b3Q7Tm8gU29sdXRpb24mcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWFjZmMgMC4wMDAwMVx1Yzc1OCBcdWMwYzFcdWIzMDBcdWM2MjRcdWNjMjhcdWIwOTggXHVjODA4XHViMzAwXHVjNjI0XHVjYzI4XHViMjk0IFx1YWNlMFx1YjgyNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTI2NzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTY2FsZWQgVHJpYW5nbGUgKExhcmdlKSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiB0d28gdHJpYW5nbGUtc2hhcGVkIHBpY3R1cmVzLiBUaGUgc2Vjb25kIHBpY3R1cmUgaXMgYSBwb3NzaWJseSB0cmFuc2xhdGVkLCByb3RhdGVkIGFuZCBzY2FsZWQgdmVyc2lvbiBvZiB0aGUgZmlyc3QuIFRoZSB0d28gdHJpYW5nbGVzIGFyZSBwbGFjZWQgb24gdGhlIHRhYmxlLCB3aXRoIHRoZSBzZWNvbmQgb25lIHBsYWNlZCBjb21wbGV0ZWx5IGluc2lkZSAocG9zc2libHkgdG91Y2hpbmcgdGhlIGJvdW5kYXJ5IG9mKSB0aGUgZmlyc3Qgb25lLiBUaGUgc2Vjb25kIHRyaWFuZ2xlIGlzIGFsd2F5cyBzY2FsZWQgYnkgYSBmYWN0b3IgdGhhdCBpcyBzdHJpY3RseSBiZXR3ZWVuIDAgYW5kIDEuPFwvcD5cclxuXHJcbjxwPllvdSBuZWVkIHRvIHByb2Nlc3MgdGhlIHBpY3R1cmUsIGFuZCBmb3IgdGhhdCB5b3UgbmVlZCBhIHBvaW50IGluIHRoZSBwaWN0dXJlIHdoaWNoIG92ZXJsYXBzIHdpdGggdGhlIHNhbWUgcG9pbnQgb2YgdGhlIHNjYWxlZCBwaWN0dXJlLiBJZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIHNvbHV0aW9uLCB5b3UgY2FuIHJldHVybiBhbnkgb2YgdGhlbS4gSWYgdGhlcmUgYXJlIG5vIHNvbHV0aW9ucywgcHJpbnQgJnF1b3Q7Tm8gU29sdXRpb24mcXVvdDsgKHdpdGhvdXQgdGhlIHF1b3RlcykgZm9yIHRoYXQgdGVzdCBjYXNlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZ2l2ZXMgdGhlIG51bWJlciBvZiBjYXNlcywmbmJzcDs8c3Ryb25nPk48XC9zdHJvbmc+LiBUaGVuIGZvciBlYWNoIHRlc3QgY2FzZSwgdGhlcmUgd2lsbCBiZSB0d28gbGluZXMsIGVhY2ggY29udGFpbmluZyBzaXggc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIC0tIHRoZSBjb29yZGluYXRlcyBvZiBvbmUgb2YgdGhlIHRyaWFuZ2xlcyAtLSBpbiB0aGUgZm9ybWF0ICZxdW90O3g8c3ViPjE8XC9zdWI+Jm5ic3A7eTxzdWI+MTxcL3N1Yj4mbmJzcDt4PHN1Yj4yPFwvc3ViPiZuYnNwO3k8c3ViPjI8XC9zdWI+Jm5ic3A7eDxzdWI+MzxcL3N1Yj4mbmJzcDt5PHN1Yj4zPFwvc3ViPiZxdW90Oy4gVGhlIHBvaW50ICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pIGluIHRoZSBmaXJzdCB0cmlhbmdsZSBjb3JyZXNwb25kcyB0byB0aGUgc2FtZSBjb3JuZXIgb2YgdGhlIHBpY3R1cmUgYXMgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPikgaW4gdGhlIHNlY29uZCB0cmlhbmdsZSwgYW5kIHNpbWlsYXJseSBmb3IgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPikgYW5kICh4PHN1Yj4zPFwvc3ViPiwgeTxzdWI+MzxcL3N1Yj4pLjxcL3A+XHJcblxyXG48cD5MaW1pdHM8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsdDs9Jm5ic3A7PHN0cm9uZz5OPFwvc3Ryb25nPiZuYnNwOyZsdDs9IDEwLjxcL2xpPlxyXG5cdDxsaT5UaGUgY29vcmRpbmF0ZXMgb2YgdGhlIHBvaW50cyB3aWxsIGJlIGludGVnZXIgbnVtYmVycyBiZXR3ZWVuIC0xMCAwMDAgYW5kIDEwIDAwMC4gVGhlIHRocmVlIHBvaW50cyBpbiBlYWNoIHRyaWFuZ2xlIHdpbGwgbm90IGJlIGNvbGxpbmVhci48XC9saT5cclxuXHQ8bGk+VGhlIHRyaWFuZ2xlcyBjYW4gaGF2ZSBhbnkgc2hhcGUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nICZxdW90O0Nhc2UgIzxzdHJvbmc+eDxcL3N0cm9uZz46ICZxdW90OyBmb2xsb3dlZCB0d28gcmVhbCBudW1iZXJzIHJlcHJlc2VudGluZyB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIG92ZXJsYXBwaW5nIHBvaW50IHNlcGFyYXRlZCBieSBvbmUgc3BhY2UgY2hhcmFjdGVyLCBvciB0aGUgc3RyaW5nICZxdW90O05vIFNvbHV0aW9uJnF1b3Q7LiBBbnN3ZXJzIHdpdGggYSByZWxhdGl2ZSBvciBhYnNvbHV0ZSBlcnJvciBvZiBhdCBtb3N0IDEwPHN1cD4tNTxcL3N1cD4mbmJzcDt3aWxsIGJlIGNvbnNpZGVyZWQgY29ycmVjdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

채점

  • 예제는 채점하지 않는다.