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 (x, y) in which we get any vertex of the polygon that is closest to (x, y).

For the first subtask all the range of points that could be on the polygon is small ((10 - (-10) + 1)^2 = 441 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 (x1, y1) and (x2, y2) such that y1 \neq y2. This means that the smallest y-coordinate is not the same as the largest y-coordinate. We can get those two points by querying points (0, -10^{18}) and (0, 10^{18}) for the vertex with the smallest and largest y-coordinate of the polygon.

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

  1. Let m be the midpoint of the line segment u and v.
  2. Draw a ray r that is perpendicular to the line segment u and v from m 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 q be some point on the ray where either its the absolute value of its x or y value is large and query that point.

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

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

A few tips when implementing. We can work with integer coordinates all the time by mapping all (x, y) \to (2x, 2y). 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;

//a query function that gets a point p in the (2x, 2y) cartesian plane
pair<long long, long long> query(pair<long long, long long> p){
    cout << "? " << p.first/2 << " " << p.second/2 << endl; //just take the integer division of the coordinates
    long long 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<long long, long long>, pair<long long, long long>>> 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
        long long dx = - p.first + q.first;
        long long dy = - p.second + q.second;
        pair<long long, long long> 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;
}

Comments

There are no comments at the moment.