시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB30252281.481%

문제

삼각형 안에 세 개의 원을 각각의 원이 다른 두 원과 삼각형의 두 변에 접하게 그릴 수 있다. 이러한 원을 말파티 원(Malfatti Circles)이라고 한다. 많은 수학자들이 말파티 원을 두 세기 이상 연구하였다. 임의의 삼각형에 대해서 말파티 원은 항상 존재하고 유일하다는 것이 증명되어 있다.

삼각형의 꼭짓점이 (20, 80), (-40, -20), (120,-20)일 때, 삼각형의 말파티 원은 다음과 같다.

  • 원의 중심이 (24.281677, 45.219486), 반지름이 21.565935
  • 원의 중심이 (3.110950, 4.409005), 반지름이 24.409005
  • 원의 중심이 (54.556724, 7.107493), 반지름이 27.107493

또, 삼각형의 꼭짓점이 (20, -20), (120, -20), (-40, 80)일 때, 삼각형의 말파티 원은 다음과 같다.

  • 원의 중심이 (25.629089, -10.057956), 반지름이 9.942044
  • 원의 중심이 (53.225883, -0.849435), 반지름이 19.150565
  • 원의 중심이 19.701191, 19.203466), 반지름이 19.913790

삼각형이 주어졌을 때, 말파티 원을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 여섯 정수 x1, y1, x2, y2, x3, y3이 공백으로 구분되어져 있다. 이 좌표는 삼각형의 각 꼭짓점이고 (x1, y1), (x2, y2), (x3, y3)이다. 입력으로 주어지는 삼각형의 꼭짓점은 반시계방향 순서이고 다음과 같은 조건을 만족한다.

  1. 모든 꼭짓점의 좌표는 -1000보다 크고 1000보다 작다.
  2. 반지름이 0.1보다 작은 말파티 원은 없다.

입력의 마지막 줄에는 0이 여섯 개 주어진다.

출력

각 테스트 케이스에 대해서 말파티 원의 반지름 r1, r2, r3를 소수점 여섯째 자리까지 출력한다. ri는 꼭짓점 (xi, yi)와 가장 가까운 원의 반지름이다.

출력하는 반지름의 오차는 0.0001보다 크면 안 된다.

예제 입력 1

20 80 -40 -20 120 -20
20 -20 120 -20 -40 80
0 0 1 0 0 1
0 0 999 1 -999 1
897 -916 847 -972 890 -925
999 999 -999 -998 -998 -999
-999 -999 999 -999 0 731
-999 -999 999 -464 -464 999
979 -436 -955 -337 157 -439
0 0 0 0 0 0

예제 출력 1

21.565935 24.409005 27.107493
9.942044 19.150565 19.913790
0.148847 0.207107 0.207107
0.125125 0.499750 0.499750
0.373458 0.383897 0.100456
0.706768 0.353509 0.353509
365.638023 365.638023 365.601038
378.524085 378.605339 378.605339
21.895803 22.052921 5.895714
W3sicHJvYmxlbV9pZCI6IjM4ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZDBcdWQzMGNcdWQyZjAgXHVjNmQwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYmNcdWFjMDFcdWQ2MTUgXHVjNTQ4XHVjNWQwIFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjNmQwXHVjNzQ0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM2ZDBcdWM3NzQgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWM2ZDBcdWFjZmMgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjQ1MCBcdWJjYzBcdWM1ZDAgXHVjODExXHVkNTU4XHVhYzhjIFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNmQwXHVjNzQ0IFx1YjlkMFx1ZDMwY1x1ZDJmMCBcdWM2ZDAoTWFsZmF0dGkgQ2lyY2xlcylcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI5Y2VcdWM3NDAgXHVjMjE4XHVkNTU5XHVjNzkwXHViNGU0XHVjNzc0IFx1YjlkMFx1ZDMwY1x1ZDJmMCBcdWM2ZDBcdWM3NDQgXHViNDUwIFx1YzEzOFx1YWUzMCBcdWM3NzRcdWMwYzEgXHVjNWYwXHVhZDZjXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM3ODRcdWM3NThcdWM3NTggXHVjMGJjXHVhYzAxXHVkNjE1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWI5ZDBcdWQzMGNcdWQyZjAgXHVjNmQwXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWFjZTAgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM5OWRcdWJhODVcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzc0ICgyMCwgODApLCAoLTQwLCAtMjApLCAoMTIwLC0yMClcdWM3N2MgXHViNTRjLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHViOWQwXHVkMzBjXHVkMmYwIFx1YzZkMFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NzQgKDI0LjI4MTY3NywgNDUuMjE5NDg2KSwgXHViYzE4XHVjOWMwXHViOTg0XHVjNzc0IDIxLjU2NTkzNTxcL2xpPlxyXG5cdDxsaT5cdWM2ZDBcdWM3NTggXHVjOTExXHVjMmVjXHVjNzc0ICgzLjExMDk1MCwgNC40MDkwMDUpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMjQuNDA5MDA1PFwvbGk+XHJcblx0PGxpPlx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NzQgKDU0LjU1NjcyNCwgNy4xMDc0OTMpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMjcuMTA3NDkzPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViNjEwLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWQzXHVjODEwXHVjNzc0ICgyMCwgLTIwKSwgKDEyMCwgLTIwKSwgKC00MCwgODApXHVjNzdjIFx1YjU0YywgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjlkMFx1ZDMwY1x1ZDJmMCBcdWM2ZDBcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM2ZDBcdWM3NTggXHVjOTExXHVjMmVjXHVjNzc0ICgyNS42MjkwODksIC0xMC4wNTc5NTYpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgOS45NDIwNDQ8XC9saT5cclxuXHQ8bGk+XHVjNmQwXHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc3NCAoNTMuMjI1ODgzLCAtMC44NDk0MzUpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMTkuMTUwNTY1PFwvbGk+XHJcblx0PGxpPlx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NzQgMTkuNzAxMTkxLCAxOS4yMDM0NjYpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMTkuOTEzNzkwPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tYWxmYXR0aS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzNweDsgd2lkdGg6NjE1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjlkMFx1ZDMwY1x1ZDJmMCBcdWM2ZDBcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzVlY1x1YzEyZiBcdWM4MTVcdWMyMTggeDEsIHkxLCB4MiwgeTIsIHgzLCB5M1x1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzAxIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc3NFx1YWNlMCAoeDEsIHkxKSwgKHgyLCB5MiksICh4MywgeTMpXHVjNzc0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgXHViYzE4XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1IFx1YzIxY1x1YzExY1x1Yzc3NFx1YWNlMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgLTEwMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwIDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMC4xXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWI5ZDBcdWQzMGNcdWQyZjAgXHVjNmQwXHVjNzQwIFx1YzVjNlx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzVlY1x1YzEyZiBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWI5ZDBcdWQzMGNcdWQyZjAgXHVjNmQwXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NCByMSwgcjIsIHIzXHViOTdjIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM1ZWNcdWMxMmZcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gcmlcdWIyOTQgXHVhZjJkXHVjOWQzXHVjODEwICh4aSwgeWkpXHVjNjQwIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjNmQwXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgMC4wMDAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM4ODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYWxmYXR0aSBDaXJjbGVzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY29uZmlndXJhdGlvbiBvZiB0aHJlZSBjaXJjbGVzIHBhY2tlZCBpbnNpZGUgYSB0cmlhbmdsZSBzdWNoIHRoYXQgZWFjaCBjaXJjbGUgaXMgdGFuZ2VudCB0byB0aGUgb3RoZXIgdHdvIGNpcmNsZXMgYW5kIHRvIHR3byBvZiB0aGUgZWRnZXMgb2YgdGhlIHRyaWFuZ2xlIGhhcyBiZWVuIHN0dWRpZWQgYnkgbWFueSBtYXRoZW1hdGljaWFucyBmb3IgbW9yZSB0aGFuIHR3byBjZW50dXJpZXMuIEV4aXN0ZW5jZSBhbmQgdW5pcXVlbmVzcyBvZiBzdWNoIGNpcmNsZXMgZm9yIGFuIGFyYml0cmFyeSB0cmlhbmdsZSBhcmUgZWFzeSB0byBwcm92ZS4gTWFueSBtZXRob2RzIG9mIG51bWVyaWNhbCBjYWxjdWxhdGlvbiBvciBnZW9tZXRyaWMgY29uc3RydWN0aW9uIG9mIHN1Y2ggY2lyY2xlcyBmcm9tIGFuIGFyYml0cmFyaWx5IGdpdmVuIHRyaWFuZ2xlIGhhdmUgYmVlbiBkaXNjb3ZlcmVkLiBUb2RheSwgc3VjaCBjaXJjbGVzIGFyZSBjYWxsZWQgdGhlIE1hbGZhdHRpIGNpcmNsZXMuPFwvcD5cclxuXHJcbjxwPkZpZ3VyZSA3IGlsbHVzdHJhdGVzIGFuIGV4YW1wbGUuIFRoZSBNYWxmYXR0aSBjaXJjbGVzIG9mIHRoZSB0cmlhbmdsZSB3aXRoIHRoZSB2ZXJ0aWNlcyAoMjAsIDgwKSwgKC00MCwgLTIwKSBhbmQgKDEyMCwgLTIwKSBhcmUgYXBwcm94aW1hdGVseTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZSBjaXJjbGUgd2l0aCB0aGUgY2VudGVyICgyNC4yODE2NzcsIDQ1LjIxOTQ4NikgYW5kIHRoZSByYWRpdXMgMjEuNTY1OTM1LDxcL2xpPlxyXG5cdDxsaT50aGUgY2lyY2xlIHdpdGggdGhlIGNlbnRlciAoMy4xMTA5NTAsIDQuNDA5MDA1KSBhbmQgdGhlIHJhZGl1cyAyNC40MDkwMDUsIGFuZDxcL2xpPlxyXG5cdDxsaT50aGUgY2lyY2xlIHdpdGggdGhlIGNlbnRlciAoNTQuNTU2NzI0LCA3LjEwNzQ5MykgYW5kIHRoZSByYWRpdXMgMjcuMTA3NDkzPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RmlndXJlIDggaWxsdXN0cmF0ZXMgYW5vdGhlciBleGFtcGxlLiBUaGUgTWFsZmF0dGkgY2lyY2xlcyBvZiB0aGUgdHJpYW5nbGUgd2l0aCB0aGUgdmVydGljZXMgKDIwLCAtMjApLCAoMTIwLCAtMjApIGFuZCAoLTQwLCA4MCkgYXJlIGFwcHJveGltYXRlbHk8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT50aGUgY2lyY2xlIHdpdGggdGhlIGNlbnRlciAoMjUuNjI5MDg5LCAtMTAuMDU3OTU2KSBhbmQgdGhlIHJhZGl1cyA5Ljk0MjA0NDxcL2xpPlxyXG5cdDxsaT50aGUgY2lyY2xlIHdpdGggdGhlIGNlbnRlciAoNTMuMjI1ODgzLCAtMC44NDk0MzUpIGFuZCB0aGUgcmFkaXVzIDE5LjE1MDU2NSwgYW5kPFwvbGk+XHJcblx0PGxpPnRoZSBjaXJjbGUgd2l0aCB0aGUgY2VudGVyICgxOS43MDExOTEsIDE5LjIwMzQ2NikgYW5kIHRoZSByYWRpdXMgMTkuOTEzNzkwLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdXIgbWlzc2lvbiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSByYWRpaSBvZiB0aGUgTWFsZmF0dGkgY2lyY2xlcyBvZiB0aGUgZ2l2ZW4gdHJpYW5nbGVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VxdWVuY2Ugb2YgZGF0YXNldHMuIEEgZGF0YXNldCBpcyBhIGxpbmUgY29udGFpbmluZyBzaXggaW50ZWdlcnMgeDEsIHkxLCB4MiwgeTIsIHgzIGFuZCB5MyBpbiB0aGlzIG9yZGVyLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlIGNvb3JkaW5hdGVzIG9mIHRoZSB2ZXJ0aWNlcyBvZiB0aGUgZ2l2ZW4gdHJpYW5nbGUgYXJlICh4MSwgeTEpLCAoeDIsIHkyKSBhbmQgKHgzLCB5MyksIHJlc3BlY3RpdmVseS4gWW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgdmVydGljZXMgZm9ybSBhIHRyaWFuZ2xlIGNvdW50ZXJjbG9ja3dpc2UuIFlvdSBjYW4gYWxzbyBhc3N1bWUgdGhhdCB0aGUgZm9sbG93aW5nIHR3byBjb25kaXRpb25zIGhvbGQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QWxsIG9mIHRoZSBjb29yZGluYXRlIHZhbHVlcyBhcmUgZ3JlYXRlciB0aGFuIC0xMDAwIGFuZCBsZXNzIHRoYW4gMTAwMC48XC9saT5cclxuXHQ8bGk+Tm9uZSBvZiB0aGUgTWFsZmF0dGkgY2lyY2xlcyBvZiB0aGUgdHJpYW5nbGUgaGFzIGEgcmFkaXVzIGxlc3MgdGhhbiAwLjEuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHNpeCB6ZXJvcyBzZXBhcmF0ZWQgYnkgYSBzcGFjZTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IGRhdGFzZXQsIHRocmVlIGRlY2ltYWwgZnJhY3Rpb25zIHIxLCByMiBhbmQgcjMgc2hvdWxkIGJlIHByaW50ZWQgaW4gYSBsaW5lIGluIHRoaXMgb3JkZXIgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSByYWRpaSBvZiB0aGUgTWFsZmF0dGkgY2lyY2xlcyBuZWFyZXN0IHRvIHRoZSB2ZXJ0aWNlcyB3aXRoIHRoZSBjb29yZGluYXRlcyAoeDEsIHkxKSwgKHgyLCB5MikgYW5kICh4MywgeTMpIHNob3VsZCBiZSByMSwgcjIgYW5kIHIzLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPk5vbmUgb2YgdGhlIG91dHB1dCB2YWx1ZXMgbWF5IGhhdmUgYW4gZXJyb3IgZ3JlYXRlciB0aGFuIDAuMDAwMS4gTm8gZXh0cmEgY2hhcmFjdGVyIHNob3VsZCBhcHBlYXIgaW4gdGhlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2009 in Tokyo G번