ECOO '21 P5 - Waldwick's Walk

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Waldwick loves sightseeing! He has started taking a long walk every morning to see various sights. On his route, he walks in a straight line from his house until he reaches a path, at which point he turns right and walks in a straight line to his first sight. After he finishes admiring the beauty of the sight, he turns right and continues to his next destination. He repeats this process until he arrives at his last destination, which is connected to the first path he walked on, so he walks on that path, turns right, and walks home.

Waldwick's sister plays a game each day where she tries to retrace Waldwick's steps to see and admire the same sights Waldwick has visited that day. She does that with the help of the GPS on Waldwick's phone where she follows Waldwick from sightseeing point to sightseeing point.

Specifically, she can travel to some integer location and the GPS will tell her the nearest point where Waldwick had reception. Since there is good GPS reception only at a visited site, the nearest point is always the closest (by straight-line distance) sight Waldwick visited. If by any chance there are multiple closest sights, the GPS may output any of them.

All of Waldwick's destinations can be represented as points on a 2D-plane, with each destination residing at a point labeled with x and y coordinate. Each day, Waldwick's sister goes to some integer location and starts using the GPS at that location. She believes that she can figure out how many sights Waldwick sees every morning using this information, but isn't exactly sure how. She wants to figure it out in the next 2000 days, before Waldwick graduates. Can you help her? It is guaranteed that Waldwick's walk contains at most 1000 locations.

Constraints

There will be at least three locations on Waldwick's walk.

All sights will have -10^9 \le x,y \le 10^9.

Subtask 1 [5%]

All sights will have -10 \le x,y \le 10.

Subtask 2 [95%]

No additional constraints.

Interaction

You can make up to 2000 queries of the form ? a b, where you tell Waldwick's sister to use the GPS at position (a,b). a and b must fit inside a 64-bit signed integer.

After such a query, the GPS (judge) will respond with two integers x y, the coordinates (x,y) of the closest sight in Waldwick's walk to (a,b).

Once you have determined the number of sights Waldwick sees, print ! n where n is the number of sights Waldwick sees, and then terminate your program.

If at any point you output an invalid query or you exceed the maximum number of queries, the judge will output 1000000001 1000000001, followed by a newline, and then exit. At this point, your program should terminate or you may get an undefined verdict. Additionally, after you output the answer, your program should exit promptly.

Note: You may have to flush the output of your program in order to communicate properly with the interactor. In Python, use sys.stdout.flush(). In C++, use std::cout << std::endl. For other languages, consult your language documentation.

Sample Interaction

> denotes the judge output. Do not print this out.

? 3 4
> 1 1
? -1 -1
> -1 -1
? 4 -4
> 1 -1
? -10 10000000
> 0 2
? 0 2
> 0 2
! 5

Explanation

Waldwick leaves his house and walks toward P. He then turns right to head toward A(1, 1), then B(1, -1), then C(-1, -1) and to D(-1, 1). He turns 45 degrees right toward E(0, 2), turns right toward P, and then turns right to head home. The 5 points on his walk are A, B, C, D and E.


Comments

There are no comments at the moment.