Probing the Disk

Time limit2sMemory limit1024 MB

Summary

Find the integer center and radius of a hidden disk in a 10^5 by 10^5 square by probing with segments and reading the lit chord length.

Level: Hard8 of 10
Topics: Geometry, Binary search, Math
Solved: No attempts yet

Problem

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 $10^5$ units long.

You cannot look into the box, but you want to know how large the disk is and where on the box bottom it is laid. The disk is a true circle with an integer radius of at least $100$ units. The distance from its center to each side of the box bottom is an integer number of units. The radius is not greater than the distance from the center to any side of the box bottom.

You can probe the disk by projecting a thin line segment of light onto the box bottom. The reflection coefficients of the disk and the box bottom differ greatly, so the overall reflection intensity tells you the length of the part of the segment that lit the disk.

Your task is to find the exact position and size of the disk through repeated probes.

Hint

Figure K.1. Sample Interaction

Examples1

Example 1

Input


60000.0000000

0.0000000

12315.3774869

Expected output

query 40000 0 40000 100000

query 0 10000 100000 10000

query 60000 60000 80000 80000

answer 40000 60000 30000