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

문제

희원이는 지난 몇 년동안 원형 시계를 수집한 수집가이다. 이 시계는 모두 거실의 한 벽에 걸려있다. 이번에 큰 돈을 벌게된 희원이는 시계를 하나 더 사려고 한다. 이때, 벽에 있는 시계의 위치를 건드리지 않으면서 매달 수 있는 가장 큰 시계를 구매하려고 한다.

벽은 너비 W, 높이 H의 직사각형 모양이다. 각 시계의 중심 좌표는 (xi, yi)이고, 반지름은 ri이다. 희원이의 시계는 벽의 경계와 겹치거나 다른 시계와 겹치지 않는다. 하지만, 서로 접할 수는 있다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 벽의 너비와 높이 W, H가 주어진다. (1 ≤ W,H ≤ 1,000,000) 다음 줄에는 벽에 걸려있는 시계의 수 C(0 ≤ C ≤ 50)가 주어진다. 다음 C개 줄에는 각 시계의 정보 xi, yi, ri가 주어진다. (ri > 0, 0 ≤ xi - ri, xi + ri ≤ W, 0 ≤ yi - ri, yi + ri ≤ H)

모든 시계의 쌍 i와 j (i ≠ j)는 (xi - xj)2 + (yi - yj)2 ≥ (ri + rj)2 를 만족한다. 

출력

각 테스트 케이스에 대해서, 희원이가 구매할 수 있는 가장 큰 시계의 반지름을 출력한다. 정답과의 오차는 10-6까지 허용한다.

예제 입력 1

1
10 10
4
2 2 1
2 8 1
8 2 1
8 8 1

예제 출력 1

3.242640687119285
W3sicHJvYmxlbV9pZCI6IjUzOTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWFjYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWM5YzBcdWIwOWMgXHViYTg3IFx1YjE0NFx1YjNkOVx1YzU0OCBcdWM2ZDBcdWQ2MTUgXHVjMmRjXHVhY2M0XHViOTdjIFx1YzIxOFx1YzlkMVx1ZDU1YyBcdWMyMThcdWM5ZDFcdWFjMDBcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWMyZGNcdWFjYzRcdWIyOTQgXHViYWE4XHViNDUwIFx1YWM3MFx1YzJlNFx1Yzc1OCBcdWQ1NWMgXHViY2JkXHVjNWQwIFx1YWM3OFx1YjgyNFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViYzg4XHVjNWQwIFx1ZDA3MCBcdWIzYzhcdWM3NDQgXHViYzhjXHVhYzhjXHViNDFjIFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWMyZGNcdWFjYzRcdWI5N2MgXHVkNTU4XHViMDk4IFx1YjM1NCBcdWMwYWNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmNiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmRjXHVhY2M0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWFjNzRcdWI0ZGNcdWI5YWNcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0XHVjMTFjIFx1YjllNFx1YjJlYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMmRjXHVhY2M0XHViOTdjIFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmNiZFx1Yzc0MCBcdWIxMDhcdWJlNDQgVywgXHViMTkyXHVjNzc0IEhcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzJkY1x1YWNjNFx1Yzc1OCBcdWM5MTFcdWMyZWMgXHVjODhjXHVkNDVjXHViMjk0ICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pXHVjNzc0XHVhY2UwLCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NDAgcjxzdWI+aTxcL3N1Yj5cdWM3NzRcdWIyZTQuIFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1Yzc1OCBcdWMyZGNcdWFjYzRcdWIyOTQgXHViY2JkXHVjNzU4IFx1YWNiZFx1YWNjNFx1YzY0MCBcdWFjYjlcdWNlNThcdWFjNzBcdWIwOTggXHViMmU0XHViOTc4IFx1YzJkY1x1YWNjNFx1YzY0MCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzExY1x1Yjg1YyBcdWM4MTFcdWQ1NjAgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNiZFx1Yzc1OCBcdWIxMDhcdWJlNDRcdWM2NDAgXHViMTkyXHVjNzc0IFcsIEhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFcsSCAmbGU7IDEsMDAwLDAwMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjYmRcdWM1ZDAgXHVhYzc4XHViODI0XHVjNzg4XHViMjk0IFx1YzJkY1x1YWNjNFx1Yzc1OCBcdWMyMTggQygwICZsZTsgQyAmbGU7IDUwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBDXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjMmRjXHVhY2M0XHVjNzU4IFx1YzgxNVx1YmNmNCB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4sIHI8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHI8c3ViPmk8XC9zdWI+ICZndDsgMCwgMCAmbGU7IHg8c3ViPmk8XC9zdWI+IC0gcjxzdWI+aTxcL3N1Yj4sIHg8c3ViPmk8XC9zdWI+ICsgcjxzdWI+aTxcL3N1Yj4gJmxlOyBXLCAwICZsZTsgeTxzdWI+aTxcL3N1Yj4gLSByPHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gKyByPHN1Yj5pPFwvc3ViPiAmbGU7IEgpPFwvcD5cclxuPHA+XHJcblx0XHViYWE4XHViNGUwIFx1YzJkY1x1YWNjNFx1Yzc1OCBcdWMzMGQgaVx1YzY0MCBqIChpICZuZTsgailcdWIyOTQgKHg8c3ViPmk8XC9zdWI+IC0geDxzdWI+ajxcL3N1Yj4pPHN1cD4yPFwvc3VwPiArICh5PHN1Yj5pPFwvc3ViPiAtIHk8c3ViPmo8XC9zdWI+KTxzdXA+MjxcL3N1cD4gJmdlOyAocjxzdWI+aTxcL3N1Yj4gKyByPHN1Yj5qPFwvc3ViPik8c3VwPjI8XC9zdXA+IFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWFjMDAgXHVhZDZjXHViOWU0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWMyZGNcdWFjYzRcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YjI5NCAxMDxzdXA+LTY8XC9zdXA+XHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1Mzk0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2xvY2tzIiwiZGVzY3JpcHRpb24iOiI8cD5EdXJpbmcgdGhlIHBhc3QgZmV3IHllYXJzIFRpbSBFLiBoYXMgYmVlbiBjb2xsZWN0aW5nIGNpcmNsZS1zaGFwZWQgY2xvY2tzIGFuZCBoZSBleHBvc2VkIHRoZW0gb24gYSBiaWcgd2FsbCBpbiBoaXMgbGl2aW5nIHJvb20uIEhlIHdhbnRzIHRvIGJ1eSBhbm90aGVyIGJpZyBjbG9jaywgYnV0IGJlY2F1c2UgaGlzIHdhbGwgaXMgYWxtb3N0IGZ1bGwgaGUgd2FudHMgdG8ga25vdyB3aGF0IHRoZSByYWRpdXMgb2YgdGhlIGJpZ2dlc3QgY2xvY2sgaXMgdGhhdCBjb3VsZCBiZSBleHBvc2VkIG9uIHRoZSB3YWxsIHdpdGhvdXQgb3ZlcmxhcHBpbmcgYW55IG90aGVyIGNsb2NrLjxcL3A+XHJcblxyXG48cD5UaGUgd2FsbCBpcyBtb2RlbGxlZCBhcyBhIHJlY3RhbmdsZSB3aXRoIHdpZHRoIFcgYW5kIGhlaWdodCBILiBGb3IgZWFjaCBjbG9jayB0aGUgY29vcmRpbmF0ZXMgKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPikgb2YgdGhlIGNlbnRyZS1wb2ludCBhbmQgdGhlIHJhZGl1cyByaSBhcmUgZ2l2ZW4uIFRoZSBjbG9ja3Mgd2lsbCBub3Qgb3ZlcmxhcCB3aXRoIHRoZSBib3VuZGFyaWVzIG9mIHRoZSB3YWxsLCBub3Igd2lsbCB0d28gY2xvY2tzIG92ZXJsYXAsIGhvd2V2ZXIgdGhleSBtaWdodCB0b3VjaCBlYWNoIG90aGVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBXIGFuZCBIIHNhdGlzZnlpbmcgMSAmbGU7IFcsSCAmbGU7IDEsMDAwLDAwMDogdGhlIHdpZHRoIGFuZCB0aGUgaGVpZ2h0IG9mIHRoZSB3YWxsLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBDIHNhdGlzZnlpbmcgMCAmbGU7IEMgJmxlOyA1MDogdGhlIG51bWJlciBvZiBjbG9ja3MuPFwvbGk+XHJcblx0PGxpPkMgbGluZXMsIGVhY2ggd2l0aCB0aHJlZSBpbnRlZ2VycyB4aSwgeWkgYW5kIHJpIHNhdGlzZnlpbmcgcjxzdWI+aTxcL3N1Yj4gJmd0OyAwLCAwICZsZTsgeDxzdWI+aTxcL3N1Yj4gJm1pbnVzOyByPHN1Yj5pPFwvc3ViPiwgeDxzdWI+aTxcL3N1Yj4gKyByPHN1Yj5pPFwvc3ViPiAmbGU7IFcsIDAgJmxlOyB5PHN1Yj5pPFwvc3ViPiAmbWludXM7IHI8c3ViPmk8XC9zdWI+IGFuZCB5PHN1Yj5pPFwvc3ViPiArIHI8c3ViPmk8XC9zdWI+ICZsZTsgSDogdGhlIGxvY2F0aW9uIGFuZCByYWRpdXMgb2YgYW4gZXhpc3RpbmcgY2xvY2suJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW50ZWdlcnMgb24gdGhlIHNhbWUgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIEZvciBhbnkgcGFpciBvZiBjbG9ja3MgaSBhbmQgaiAoaSAmbmU7IGopLCAoeDxzdWI+aTxcL3N1Yj4gJm1pbnVzOyB4PHN1Yj5qPFwvc3ViPik8c3VwPjI8XC9zdXA+ICsgKHk8c3ViPmk8XC9zdWI+ICZtaW51czsgeTxzdWI+ajxcL3N1Yj4pPHN1cD4yPFwvc3VwPiAmZ2U7IChyPHN1Yj5pPFwvc3ViPiArIHI8c3ViPmo8XC9zdWI+KTxzdXA+MjxcL3N1cD4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGV2ZXJ5IHRlc3QgY2FzZSBpbiB0aGUgaW5wdXQsIHRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYSBzaW5nbGUgcmVhbCBudW1iZXIsIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSBtYXhpbXVtIHJhZGl1cyBvZiBhIGNsb2NrIHRoYXQgXHVmYjAxdHMgb24gdGhlIHdhbGwgd2l0aG91dCBvdmVybGFwcGluZyB3aXRoIGFueSBleGlzdGluZyBjbG9jayBvciB0aGUgYm91bmRhcmllcyBvZiB0aGUgd2FsbC48XC9wPlxyXG5cclxuPHA+WW91ciBhbnN3ZXIgc2hvdWxkIGhhdmUgZWl0aGVyIGFuIGFic29sdXRlIG9yIGEgcmVsYXRpdmUgZXJyb3Igb2YgYXQgbW9zdCAxMDxzdXA+Jm1pbnVzOzY8XC9zdXA+LiBNYWtlIHN1cmUgdGhhdCB5b3UgcHJpbnQgZW5vdWdoIGRlY2ltYWxzLiBJbiBwYXJ0aWN1bGFyLCBpZiB5b3UgcHJvZ3JhbSBpbiBDKyssIGRvIG5vdCB1c2UgcGxhaW4gY291dCAmbHQ7Jmx0OyBNICZsdDsmbHQ7IGVuZGw7IHRvIG91dHB1dCB5b3VyIGFuc3dlciAoYSBkb3VibGUpIE0sIGJlY2F1c2UgdGhpcyBzb21ldGltZXMgcHJvZHVjZXMgdG9vIGZldyBkZWNpbWFscy4gSW5zdGVhZCwgeW91IG1heSB1c2UgcHJpbnRmICgmcXVvdDslbGZcXG4mcXVvdDssIE0pOyAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==