시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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.

  • Megumin won’t hurt herself while casting Explosion. That is, (x − cx)2 + (y − cy)2 > r2.
  • All the other trees must disappear after Megumin’s Explosion. That is, for any i such that (xi, yi) ̸= (x, y), we have (xi − cx)2 + (yi − cy)2 ≤ r2.

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.

제한

  • 1 < n ≤ 50000
  • 1 ≤ r ≤ 107
  • x, y ∈ [−107, 107]
  • Your output may not contain any string token longer than 100 characters.
  • You may need to use __int128 and __float128 if you use C/C++.
  • You may need to use BigInteger and BigDecimal if you use Java/Kotlin.
  • Your output will be checked by a Java program using BigDecimal with a 256-digit precision.
  • There always exists a solution which can be represented in the given format.

예제 입력 1

4 1
1 0
0 1
2 2
3 3

예제 출력 1

-1

예제 입력 2

4 1
0 0
1 1
0 2
1 0

예제 출력 2

1 0
0 1

예제 입력 3

5 1
0 0
1 1
1 0
0 1
2 2

예제 출력 3

2 2
0.5 0.5