시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 8 8 61.538%

문제

삼각형 안에 세 개의 원을 각각의 원이 다른 두 원과 삼각형의 두 변에 접하게 그릴 수 있다. 이러한 원을 말파티 원(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+XHJcblxyXG48cD5cdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWMwXHVjODEwXHVjNzc0ICgyMCwgODApLCAoLTQwLCAtMjApLCAoMTIwLC0yMClcdWM3N2MgXHViNTRjLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHViOWQwXHVkMzBjXHVkMmYwIFx1YzZkMFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NzQgKDI0LjI4MTY3NywgNDUuMjE5NDg2KSwgXHViYzE4XHVjOWMwXHViOTg0XHVjNzc0IDIxLjU2NTkzNTxcL2xpPlxyXG5cdDxsaT5cdWM2ZDBcdWM3NTggXHVjOTExXHVjMmVjXHVjNzc0ICgzLjExMDk1MCwgNC40MDkwMDUpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMjQuNDA5MDA1PFwvbGk+XHJcblx0PGxpPlx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NzQgKDU0LjU1NjcyNCwgNy4xMDc0OTMpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMjcuMTA3NDkzPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViNjEwLCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhZjJkXHVjOWMwXHVjODEwXHVjNzc0ICgyMCwgLTIwKSwgKDEyMCwgLTIwKSwgKC00MCwgODApXHVjNzdjIFx1YjU0YywgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjlkMFx1ZDMwY1x1ZDJmMCBcdWM2ZDBcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM2ZDBcdWM3NTggXHVjOTExXHVjMmVjXHVjNzc0ICgyNS42MjkwODksIC0xMC4wNTc5NTYpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgOS45NDIwNDQ8XC9saT5cclxuXHQ8bGk+XHVjNmQwXHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc3NCAoNTMuMjI1ODgzLCAtMC44NDk0MzUpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMTkuMTUwNTY1PFwvbGk+XHJcblx0PGxpPlx1YzZkMFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NzQgMTkuNzAxMTkxLCAxOS4yMDM0NjYpLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMTkuOTEzNzkwPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tYWxmYXR0aS5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzNweDsgd2lkdGg6NjE1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjlkMFx1ZDMwY1x1ZDJmMCBcdWM2ZDBcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzVlY1x1YzEyZiBcdWM4MTVcdWMyMTggeDEsIHkxLCB4MiwgeTIsIHgzLCB5M1x1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzAxIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc3NFx1YWNlMCAoeDEsIHkxKSwgKHgyLCB5MiksICh4MywgeTMpXHVjNzc0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NDAgXHViYzE4XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1IFx1YzIxY1x1YzExY1x1Yzc3NFx1YWNlMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgLTEwMDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhY2UwIDEwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMC4xXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWI5ZDBcdWQzMGNcdWQyZjAgXHVjNmQwXHVjNzQwIFx1YzVjNlx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzVlY1x1YzEyZiBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWI5ZDBcdWQzMGNcdWQyZjAgXHVjNmQwXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NCByMSwgcjIsIHIzXHViOTdjIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWM1ZWNcdWMxMmZcdWM5ZjggXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gcmlcdWIyOTQgXHVhZjJkXHVjOWMwXHVjODEwICh4aSwgeWkpXHVjNjQwIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjNmQwXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgMC4wMDAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzg4MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hbGZhdHRpIENpcmNsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb25maWd1cmF0aW9uIG9mIHRocmVlIGNpcmNsZXMgcGFja2VkIGluc2lkZSBhIHRyaWFuZ2xlIHN1Y2ggdGhhdCBlYWNoIGNpcmNsZSBpcyB0YW5nZW50IHRvIHRoZSBvdGhlciB0d28gY2lyY2xlcyBhbmQgdG8gdHdvIG9mIHRoZSBlZGdlcyBvZiB0aGUgdHJpYW5nbGUgaGFzIGJlZW4gc3R1ZGllZCBieSBtYW55IG1hdGhlbWF0aWNpYW5zIGZvciBtb3JlIHRoYW4gdHdvIGNlbnR1cmllcy4gRXhpc3RlbmNlIGFuZCB1bmlxdWVuZXNzIG9mIHN1Y2ggY2lyY2xlcyBmb3IgYW4gYXJiaXRyYXJ5IHRyaWFuZ2xlIGFyZSBlYXN5IHRvIHByb3ZlLiBNYW55IG1ldGhvZHMgb2YgbnVtZXJpY2FsIGNhbGN1bGF0aW9uIG9yIGdlb21ldHJpYyBjb25zdHJ1Y3Rpb24gb2Ygc3VjaCBjaXJjbGVzIGZyb20gYW4gYXJiaXRyYXJpbHkgZ2l2ZW4gdHJpYW5nbGUgaGF2ZSBiZWVuIGRpc2NvdmVyZWQuIFRvZGF5LCBzdWNoIGNpcmNsZXMgYXJlIGNhbGxlZCB0aGUgTWFsZmF0dGkgY2lyY2xlcy48XC9wPlxyXG5cclxuPHA+RmlndXJlIDcgaWxsdXN0cmF0ZXMgYW4gZXhhbXBsZS4gVGhlIE1hbGZhdHRpIGNpcmNsZXMgb2YgdGhlIHRyaWFuZ2xlIHdpdGggdGhlIHZlcnRpY2VzICgyMCwgODApLCAoLTQwLCAtMjApIGFuZCAoMTIwLCAtMjApIGFyZSBhcHByb3hpbWF0ZWx5PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+dGhlIGNpcmNsZSB3aXRoIHRoZSBjZW50ZXIgKDI0LjI4MTY3NywgNDUuMjE5NDg2KSBhbmQgdGhlIHJhZGl1cyAyMS41NjU5MzUsPFwvbGk+XHJcblx0PGxpPnRoZSBjaXJjbGUgd2l0aCB0aGUgY2VudGVyICgzLjExMDk1MCwgNC40MDkwMDUpIGFuZCB0aGUgcmFkaXVzIDI0LjQwOTAwNSwgYW5kPFwvbGk+XHJcblx0PGxpPnRoZSBjaXJjbGUgd2l0aCB0aGUgY2VudGVyICg1NC41NTY3MjQsIDcuMTA3NDkzKSBhbmQgdGhlIHJhZGl1cyAyNy4xMDc0OTM8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5GaWd1cmUgOCBpbGx1c3RyYXRlcyBhbm90aGVyIGV4YW1wbGUuIFRoZSBNYWxmYXR0aSBjaXJjbGVzIG9mIHRoZSB0cmlhbmdsZSB3aXRoIHRoZSB2ZXJ0aWNlcyAoMjAsIC0yMCksICgxMjAsIC0yMCkgYW5kICgtNDAsIDgwKSBhcmUgYXBwcm94aW1hdGVseTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZSBjaXJjbGUgd2l0aCB0aGUgY2VudGVyICgyNS42MjkwODksIC0xMC4wNTc5NTYpIGFuZCB0aGUgcmFkaXVzIDkuOTQyMDQ0PFwvbGk+XHJcblx0PGxpPnRoZSBjaXJjbGUgd2l0aCB0aGUgY2VudGVyICg1My4yMjU4ODMsIC0wLjg0OTQzNSkgYW5kIHRoZSByYWRpdXMgMTkuMTUwNTY1LCBhbmQ8XC9saT5cclxuXHQ8bGk+dGhlIGNpcmNsZSB3aXRoIHRoZSBjZW50ZXIgKDE5LjcwMTE5MSwgMTkuMjAzNDY2KSBhbmQgdGhlIHJhZGl1cyAxOS45MTM3OTAuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91ciBtaXNzaW9uIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgdGhlIHJhZGlpIG9mIHRoZSBNYWxmYXR0aSBjaXJjbGVzIG9mIHRoZSBnaXZlbiB0cmlhbmdsZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBkYXRhc2V0cy4gQSBkYXRhc2V0IGlzIGEgbGluZSBjb250YWluaW5nIHNpeCBpbnRlZ2VycyB4MSwgeTEsIHgyLCB5MiwgeDMgYW5kIHkzIGluIHRoaXMgb3JkZXIsIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBUaGUgY29vcmRpbmF0ZXMgb2YgdGhlIHZlcnRpY2VzIG9mIHRoZSBnaXZlbiB0cmlhbmdsZSBhcmUgKHgxLCB5MSksICh4MiwgeTIpIGFuZCAoeDMsIHkzKSwgcmVzcGVjdGl2ZWx5LiBZb3UgY2FuIGFzc3VtZSB0aGF0IHRoZSB2ZXJ0aWNlcyBmb3JtIGEgdHJpYW5nbGUgY291bnRlcmNsb2Nrd2lzZS4gWW91IGNhbiBhbHNvIGFzc3VtZSB0aGF0IHRoZSBmb2xsb3dpbmcgdHdvIGNvbmRpdGlvbnMgaG9sZC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BbGwgb2YgdGhlIGNvb3JkaW5hdGUgdmFsdWVzIGFyZSBncmVhdGVyIHRoYW4gLTEwMDAgYW5kIGxlc3MgdGhhbiAxMDAwLjxcL2xpPlxyXG5cdDxsaT5Ob25lIG9mIHRoZSBNYWxmYXR0aSBjaXJjbGVzIG9mIHRoZSB0cmlhbmdsZSBoYXMgYSByYWRpdXMgbGVzcyB0aGFuIDAuMS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgc2l4IHplcm9zIHNlcGFyYXRlZCBieSBhIHNwYWNlPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgZGF0YXNldCwgdGhyZWUgZGVjaW1hbCBmcmFjdGlvbnMgcjEsIHIyIGFuZCByMyBzaG91bGQgYmUgcHJpbnRlZCBpbiBhIGxpbmUgaW4gdGhpcyBvcmRlciBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlIHJhZGlpIG9mIHRoZSBNYWxmYXR0aSBjaXJjbGVzIG5lYXJlc3QgdG8gdGhlIHZlcnRpY2VzIHdpdGggdGhlIGNvb3JkaW5hdGVzICh4MSwgeTEpLCAoeDIsIHkyKSBhbmQgKHgzLCB5Mykgc2hvdWxkIGJlIHIxLCByMiBhbmQgcjMsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+Tm9uZSBvZiB0aGUgb3V0cHV0IHZhbHVlcyBtYXkgaGF2ZSBhbiBlcnJvciBncmVhdGVyIHRoYW4gMC4wMDAxLiBObyBleHRyYSBjaGFyYWN0ZXIgc2hvdWxkIGFwcGVhciBpbiB0aGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==