Probing the Disk

면접 대비

시간 제한2초메모리 제한1024 MB

요약
한 변의 길이가 10^5인 정사각형 안에 놓인 원판에 선분을 쏘아, 정수인 중심 좌표와 반지름을 적은 횟수의 질의로 알아낸다.
난이도

보통10점 중 6점

유형
기하, 이분 탐색, 수학, 구현
정답자
아직 제출이 없습니다

문제

This is an interactive problem.

A thin black disk is laid flat on the square bottom of a white box. The sides of the box bottom are 10510^5 units long.

Somehow, you are not allowed to look into the box, but you want to know how large the disk is and where in the box bottom the disk is laid. You know that the shape of the disk is a true circle with an integer units of radius, not less than 100100 units, and its center is integer units distant from the sides of the box bottom. The radius of the disk is, of course, not greater than the distances of the center of the disk from any of the sides of the box bottom.

You can probe the disk by projecting a thin line segment of light to the box bottom. As the reflection coefficients of the disk and the box bottom are quite different, from the overall reflection intensity, you can tell the length of the part of the segment that lit the disk.

Your task is to decide the exact position and size of the disk through repetitive probes.

힌트

Figure K.1. Sample Interaction

예제1

  1. 예제 1

    입력
    
60000.0000000

0.0000000

12315.3774869
    예상 출력
    query 40000 0 40000 100000

query 0 10000 100000 10000

query 60000 60000 80000 80000

answer 40000 60000 30000