시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 0 | 0 | 0 | 0.000% |
In the Konosuba World, Megumin is a famous archwizard for her trademark Explosion magic. She must cast Explosion once a day or die. Her Explosion magic is extremely powerful and consumes a lot of energy. Megumin can only cast Explosion once a day, and she always becomes exhausted after casting Explosion. That is why her teammate Kazuma always carries her home and worries about her.
Today, Megumin practices her Explosion on a plain area. There are n trees on the plain, and the i-th tree is located at (xi, yi) for 1 ≤ i ≤ n. You may assume that (xi, yi) ̸= (xj, yj) for i ̸= j. Megumin wants to find a tree to stand on its top, then cast her Explosion with the longest spell in the Konosuba World. Her Explosion can destroy everything within a circular area of radius r. That is, if the area is centered at (cx, cy) and a tree is located at (x, y) where (x − cx)2 + (y − cy)2 ≤ r2, then the tree will disappear after Megumin’s Explosion.
Kazuma is trying to find an ideal way for Megumin to cast Explosion. Assume that Megumin stands on the top of the tree located at (x, y) and then casts Explosion on the circular area centered at (cx, cy). This way is ideal if it satisfies the following conditions.
Please help Kazuma to find out an ideal way. If there is no such way for Megumin to cast, output −1. Otherwise, please tell Kazuma where the tree for Megumin to stand and the center of Megumin’s Explosion are.
The first line contains two integers n and r. n is the number of the trees, and r is the radius of Explosion. The following n lines describe the positions of the trees. Each of them contains two integers x and y, and the corresponding tree is located at (x, y).
If there is no ideal way, output −1 on a line. Otherwise, output two lines. The first line contains two integers x and y separated by a blank. Megumin can safely cast Explosion on the top of the tree at (x, y). The second line contains two real numbers cx and cy separated by a blank. Megumin should cast Explosion certered at (cx, cy) to destroy all the other trees. Please note that cx and cy may be fractional numbers.
__int128
and __float128
if you use C/C++.BigInteger
and BigDecimal
if you use Java/Kotlin.BigDecimal
with a 256-digit precision.4 1 1 0 0 1 2 2 3 3
-1
4 1 0 0 1 1 0 2 1 0
1 0 0 1
5 1 0 0 1 1 1 0 0 1 2 2
2 2 0.5 0.5
ICPC > Regionals > Asia Pacific > Taiwan > Taiwan Online Programming Contest > TOPC 2019 E번