[Solution] Crop Squares solution codeforces

Table of Contents

Crop Squares solution codeforces

Crop Squares solution codeforces – Farmer Stanley grows corn on a rectangular field of size 𝑛×𝑚n×m meters with corners in points (0,0)(0,0)(0,𝑚)(0,m)(𝑛,0)(n,0)(𝑛,𝑚)(n,m). This year the harvest was plentiful and corn covered the whole field.

The night before harvest aliens arrived and poisoned the corn in a single 1×11×1 square with sides parallel to field borders. The corn inside the square must not be eaten, but you cannot distinguish it from ordinary corn by sight. Stanley can only collect a sample of corn from an arbitrary polygon and bring it to the laboratory, where it will be analyzed and Stanley will be told the amount of corn in the sample that was poisoned. Since the harvest will soon deteriorate, such a study can be carried out no more than 55 times.

[Solution] Crop Squares solution codeforces

More formally, it is allowed to make no more than 55 queries, each of them calculates the area of intersection of a chosen polygon with a square of poisoned corn. It is necessary to find out the coordinates of the lower-left corner of the drawn square (the vertex of the square with the smallest 𝑥x and 𝑦y coordinates).

Input

First line contains two integers 𝑛n and 𝑚m (1𝑛,𝑚1001≤n,m≤100) — field sizes.

Interaction

In order to query the area of intersection of a polygon with 𝑘k (3𝑘10003≤k≤1000) vertices at points with coordinates (𝑥1,𝑦1),,(𝑥𝑘,𝑦𝑘)(x1,y1),…,(xk,yk) with a square of poisoned corn print 𝑘+1k+1 lines. In the first of these lines print “? k“. In the 𝑖i-th of the next 𝑘k lines print two real numbers 𝑥𝑖xi and 𝑦𝑖yi (|𝑥𝑖|,|𝑦𝑖|104|xi|,|yi|≤104) with at most 1515 digits after decimal place.

The polygon must have strictly positive area and contain no self-intersections.

In response to this query you will receive a real number 𝑠s (0𝑠10≤s≤1) with 1515 digits after decimal place — the area of intersection of the square with the given polygon. If the polygon is invalid, there is no guarantee on the valid response.

When you have identified the drawn square, print on a separate line “! x y“, where 𝑥x and 𝑦y are real numbers with at most 1515 digits after decimal place representing the coordinates of its lower-left corner (0𝑥𝑛10≤x≤n−10𝑦𝑚10≤y≤m−1), and then you have to terminate your program.

Your answer will be considered correct if its absolute or relative error on both coordinates does not exceed 10610−6. Formally let your answer be 𝑎a, jury answer be 𝑏b. Your answer will be considered correct if |𝑎𝑏|𝑚𝑎𝑥(1,|𝑏|)106|a−b|max(1,|b|)≤10−6.

[Solution] Crop Squares solution codeforces

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

Hacks

To make a hack, use the following test format.

The first line of the input should contain two integers 𝑛n and 𝑚m (1𝑛,𝑚1001≤n,m≤100) — field sizes.

The second line should contain two real numbers 𝑥x (0𝑥𝑛10≤x≤n−1) and 𝑦y (0𝑦𝑚10≤y≤m−1) — coordinates of the lower-left corner of the square of poisoned corn.

Example
input

Copy
3 3





0.5





0.5
output

Copy
? 4
0 0
2 0
2 3
0 3

? 4
0 0
0 1
3 1
3 0

! 1.5 0.5

[Solution] Crop Squares solution codeforces

In the first test from the statement, the aliens poisoned a square of corn with vertices at points with coordinates (1.5,0.5)(1.5,0.5)(1.5,1.5)(1.5,1.5)(2.5,1.5)(2.5,1.5)(2.5,0.5)(2.5,0.5). In the picture, it is red, the polygon selected in the query is blue, and their intersection is green.

Picture for the first query:

Picture for the second query:

For Solution

“Click Here”

Leave a Comment