ACM-ICPC SEERC 2014 Problem E

Wanted to do a writeup of Problem E in this year's Southeastern European Regional Contest of ACM-ICPC. Even though it was the 4th most solved question in the round, it was not intuitive to any member of my team. After thinking over the cues provided in the problem analysis session that took place following the contest, I believe I reached a point to let me code a solution. I also wanted to discuss the theory I based my code on, in hopes that it can be corrected by others if wrong, and can help others understand the problem if/once it is correct. Once I find the time, I plan to add some diagrams/illustrations to clarify a couple of points in Ideas&Facts and The Solution sections of this post. So let's start with the problem statement

Problem Statement

Peter and Bob are playing a "Points" game on a math sheet of paper. Peter places a few points on the paper - grid nodes. Bob wants to surround them with a polygon so that all marked nodes are laying strictly within (not at the border) the polygon. All sides of the polygon are along the sides or the diagonals of the grid cells and its perimeter is as small as possible. You must determine what is the perimeter of the polygon.

Input

The first line of the input file contains integer N - the number of points placed by Peter (1 <= N <= 100,000) Each of following N lines contains two integers xi, yi - the point coordinates placed by Peter. The coordinates by absolute value do not exceed 106. Some points can match.

Output

You need to print one number - the perimeter of the required polygon. The answer should be printed with accuracy not less than 0.001.

Sample Cases

Input:
1
0 0
Output:
5.656
Input:
2
1 1
1 2
Output:
7.656854

Ideas & Facts

The question involves finding a polygon that encloses all the given points on the plane. The constraint to this polygon is that its sides need to be either parallel to the axes of the coordinate system or have to make 45 degrees with one of them. The question statement also asks us to find a polygon with the minimal perimeter. There are a few key aspects to such a polygon that one needs to notice before getting to a solution, and an informal proof for all such takeaways I could think of are provided below.

The first thing to notice is that the polygon we are looking for is convex. Assume that the p olygon may be concave and consider a concave section in it. The argument that invalidates the possiblity of such a concavic section is the fact that connecting the endpoints of the said section costs less, thereby producing a polygon with smaller perimeter. Thus, all such concavic section on a polygon need to be corrected this way to minimize its perimeter.

A second fact we will need to keep in mind in the following sections is the fact that all convex polygons, and not just the uniform ones, have a total of 360 degrees of exterior angles.

A third thing to note is that the corners of the polygon we are looking for will have interior angles of 45, 90 or 135 degrees, as it can only have horizontal, vertical or 45 degrees inclined lines as sides.

The next claim will sound a little too irrelevant, but it is important to note. We can claim that the convex polygon we are looking for can have not more than 8 corners. The proof follows from the two things we observed earlier. As the number of sides increase in a convex polygon, the interior angles must increase, or in other words, the exterior angle between neighboring two sides must decrease, as any convex polygon can have 360 degrees of total exterior angles. Understanding of this greedy strategy (i.e. keeping the exterior angles small to increase the number of corners we can have in a convex polygon) should serve sufficient to prove the claim. Consider that we want to draw the polygon with the most sides that complies with the constraints given in the question statement. The interior angle between consecutive edges can be 45, 90 or 135 degrees. In those cases, the exterior angle will be 135, 90 and 45 degrees, respectively. If we do the greedy thing and choose to draw each of our corners in such a way that each of them has minimal exterior angles, then we can not draw a polygon with more than (360 / 45) = 8 corners as we will have exhausted all 360 degrees of exterior angle any convex polygon could have.

The Solution

The solution is derived from the idea that all the points are to lie within a bounding rectangle with sides located at minimal and maximal x and y coordinates. (xMin - 1, xMax + 1, yMin - 1, and yMax + 1, to be exact) We want to cut off the unnecessary parts of this bounding rectangle to make the perimeter of this bounding polygon optimal. As we need a single polygon with just one face, we can not cut or make a hole from the middle. We can only cut from the sides. As the coordinates of the sides are pretty optimal (i.e. increasing min or decreasing max sides would cause a point to lie on the polygon's edge, which is not allowed) the only part of the rectangle we can optimize is its corners. We are only allowed to make diagonal cuts to the corners, so we should find the closest point to each corner and cut the corner diagonally based on the distance of this closest point to the corner we are cutting.

The end product of the 4 cuts is a convex polygon with at most 8 sides, and more importantly, that polygon has the most minimal perimeter. The formal proof may be a little deeper, mathematically, but the following intuitive approach should sufficiently serve as an informal proof. If we moved one of the bounding polygon's horizontal and vertical sides, towards the one it's facing, one of the points will be on the border of the polygon. Also, if we made our diagonal cuts on the corners sqrt(2)/2 deeper, we would again cause a point to end up on the border of the polygon. Reconsidering the fact that the polygon we are looking to find having at most 8 sides & corners should come in handy now to further digest this fact.

Complexity

The algorithm described above does not require sorting the points provided as input. Finding the maximal and minimal coordinates of all points on x and y axes as well as finding the closest point to another among N points require O(N) complexity. The overall complexity is, then, O(N).

Code

As the test cases are not publicly available for us to test my code, I could not claim that this solution would get an ACCEPTED. However, it seems to be passing a couple of dozens of test cases I put this code through.

#include <cstdio>
#include <climits>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

vector< pair<int, int> > pts;

pair<int, int> findClosestPoint(pair<int, int> point)  
{
    int n = pts.size();
    double tmp, minDist = 2000000.0;;
    pair<int, int> closest;
    closest = pts[0];

    for(int i=0; i < n; ++i)
    {
        tmp = sqrt(pow(point.first - pts[i].first, 2.0) +
                   pow(point.second - pts[i].second, 2.0));
        if(tmp < minDist)
        {
            closest = pts[i];
            minDist = tmp;
        }
    }

    return closest;
}

int main()  
{
    int n;
    int xMin, xMax, yMin, yMax;
    int triangleTLLen, triangleTRLen,
        triangleBLLen, triangleBRLen, totalTriangleLengths;
    double result;
    pair<int, int> bBoxTL, bBoxTR, bBoxBL, bBoxBR;
    pair<int, int> closestTL, closestTR, closestBL, closestBR;

    xMin = yMin = INT_MAX;
    xMax = yMax = INT_MIN;

    scanf("%d", &n);
    pts.resize(n);
    for(int i=0; i < n; ++i)
    {
        scanf("%d%d", &pts[i].first, &pts[i].second);
        if(pts[i].first > xMax)
            xMax = pts[i].first;

        if(pts[i].first < xMin)
            xMin = pts[i].first;

        if(pts[i].second > yMax)
            yMax = pts[i].second;

        if(pts[i].second < yMin)
            yMin = pts[i].second;
    }
    --xMin;
    --yMin;
    ++xMax;
    ++yMax;

    bBoxTL = make_pair(xMin, yMax);
    bBoxTR = make_pair(xMax, yMax);
    bBoxBL = make_pair(xMin, yMin);
    bBoxBR = make_pair(xMax, yMin);

    closestTL = findClosestPoint(bBoxTL);
    closestTR = findClosestPoint(bBoxTR);
    closestBL = findClosestPoint(bBoxBL);
    closestBR = findClosestPoint(bBoxBR);

    triangleTLLen = abs(bBoxTL.first - closestTL.first) +
                    abs(bBoxTL.second - closestTL.second) - 1;
    triangleTRLen = abs(bBoxTR.first - closestTR.first) +
                    abs(bBoxTR.second - closestTR.second) - 1;
    triangleBLLen = abs(bBoxBL.first - closestBL.first) +
                    abs(bBoxBL.second - closestBL.second) - 1;
    triangleBRLen = abs(bBoxBR.first - closestBR.first) +
                    abs(bBoxBR.second - closestBR.second) - 1;
    totalTriangleLengths = triangleTLLen + triangleTRLen +
                           triangleBLLen + triangleBRLen;

    result = 2 * ((xMax - xMin) + (yMax - yMin) -
                  totalTriangleLengths) +
             sqrt(2) * totalTriangleLengths;
    printf("%lf\n", result);

    return 0;
}

Testing

As I mentioned above, the test cases of the competition are not publicly available at the moment. So, for the time being, I can not completely verify if the code above will solve the question for all inputs. Still, I think the idea behind my solution is correct. Feel free to contact me for any correction or clarification you feel is in order. I do not have a comments section for my posts yet, but you can get in touch with me on Twitter.

Thanks

Even though we did not get a good placement at the contest, the event itself was quite exciting. Even though there is a general conception of Ukraine being a country in chaos these days, thanks to Mesyura, and our interpreters in our experience it was a country thriving in computer science, as well as many other areas. Congratulations, again, to LNU Penguins, the top team in this year's SEERC, and their coach Vasyl, who is another figure, if not the most important one, who made our trip to Ukraine worth our while.