## Editorial for ECOO '21 P5 - Waldwick's Walk

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AQT

The problem is asking to find all the vertices to a non-degenerate convex polygon. We can try to find all the vertices by asking the judge a point in which we get any vertex of the polygon that is closest to .

For the first subtask all the range of points that could be on the polygon is small ( possible candidates). A sufficient algorithm for the first subtask is to query all points in the range and maintain a counter of all the times the queried point is equal to the point that has been returned.

For the other subtask, we note that a convex polygon must have two points and such that . This means that the smallest -coordinate is not the same as the largest -coordinate. We can get those two points by querying points and for the vertex with the smallest and largest -coordinate of the polygon.

Now consider, this method of constructing a polygon, knowing that we have at least vertices and . We will now check if and are adjacent. For and to be adjacent, then all the vertices must strictly lie on one side of the line and . So, if there exist a point on the other side of the line, then and are not adjacent. We can try to find this point by using the following method.

1. Let be the midpoint of the line segment and .
2. Draw a ray that is perpendicular to the line segment and from and extends towards the plane where a new point might potentially exist (the half-plane that does not contain the rest of the known points of the convex polygon).
3. Let be some point on the ray where either the absolute value of its or value is large and query that point.

Note that point that is being returned as . If is equal to either or , then we have not found any point between and . Otherwise, and are not adjacent as is between, so we will repeat this process for the pairs and and and .

Since, every edge and every vertex of the polygon will use up a query, then we need to use queries to find all the points.

A few tips when implementing. We can work with integer coordinates all the time by mapping all . This way the midpoints will all have integer coordinates. Also, by repeating the process, we can think of it as divide and conquering on a polygon, so we can write it recursively or iteratively. Below is my implementation in C++ which is iterative.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

//a query function that gets a point p in the (2x, 2y) cartesian plane
pair<ll, ll> query(pair<ll, ll> p){
cout << "? " << p.first/2 << " " << p.second/2 << endl; //just take the integer division of the coordinates
ll x, y;
cin >> x >> y;
//mapping to them to (2x, 2y)
x *= 2;
y *= 2;
return make_pair(x, y);
}

int main(){
auto p = query(make_pair(0, 1000000000000000LL)); //vertex with the largest y coordinate
auto q = query(make_pair(0, -1000000000000000LL)); //vertex with the smallest y coordinate
int ans = 2; //our answer so far is at least 2
queue<pair<pair<ll, ll>, pair<ll, ll>>> qu; //queue for all the pairs (u, v) that we need to process
//we have to try both sides of p and q
qu.push(make_pair(p, q));
qu.push(make_pair(q, p));
//while there are more pairs to be processed
while(qu.size()){
//p is u and q is v in our case
//testing to see if p is beside q in the polygon and q is clockwise to p in the polygon
auto p = qu.front().first;
auto q = qu.front().second;
qu.pop();
//what we are going to add to the midpoint to get the point that is going to be queried
ll dx = - p.first + q.first;
ll dy = - p.second + q.second;
pair<ll, ll> m = make_pair((p.first + q.first)/2, (p.second+q.second)/2); //midpoint of segment p and q
//making the point to be as large as possible
while(abs(dx) < 1000000000000000LL && abs(dy) < 1000000000000000LL){
dx += dx;
dy += dy;
}
//(-dy + m.first, dx + m.second) is the querying point
//this gets the query point
auto t = query(make_pair(-dy+m.first, dx+m.second));
//if p and q are not adjacent, we will break it down into smaller processes
if(t != p && t != q){
ans++; //t is the new point
qu.push(make_pair(p, t)); //new pair (p, t)
qu.push(make_pair(t, q)); //new pair (t, q)
}
}
cout << "! " << ans << endl;
}