USACO 5.1 Fencing The Cows

The answer is the perimeter of the convex hull of all the grazing points. Use Graham Scan to calculate the convex hull, because it’s efficient and easy to implement:

• First, pick a point that has smallest x coordinate. Use y coordinate to break ties if necessary. Let’s call this point the base point.
• Then iterate for the rest of the points, calculate the polar angle between the current point and the base point.
• Now we get all points and their polar angles with respect to the base point, sort these points based on polar angle.
• Walk through the sorted points and make sure a new point only appear in the counter clock wise direction (turn left) of the current point. Add the new point to the result, and drop old points if necessary.
• We should now have a convex hull point sets available. Calculate the perimeter is now trivial.

This implementation also dealt with degenerated case where the points are co-linear.

#include <vector>
#include <iostream>
#include <fstream>
#include <limits>
#include <algorithm>
#include <cmath>
#include <stack>
#include <iomanip>

using namespace std;

int N;
struct Point {
    double x; double y; double pa /* Polar Angle with reference point. */;
};
vector<Point> points;

double dist(Point &a, Point &b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

bool ccw(Point &a, Point &b, Point &c) {
    double area = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
    if (area > 0) {
        return true;
    } else {
        return false;
    }
}

double graham_scan() {
    double ans = 0;
    stack<Point> stack;
    stack.push(points[0]);
    stack.push(points[1]);
    stack.push(points[2]);
    
    for (int i = 3; i < N; i++) {
        Point top = stack.top();
        stack.pop();
        while (!ccw(stack.top(), top, points[i]))   {
            top = stack.top();
            stack.pop();
        }
        stack.push(top);
        stack.push(points[i]);
    }
    
    // Save the last point to close the hull with p0.
    Point p1 = stack.top(); stack.pop();
    Point cur = p1;
    while (!stack.empty()) {
        ans += dist(cur, stack.top());
        cur = stack.top(); stack.pop();
    }
    ans += dist(cur, p1);
    return ans;
}

int main() {
    ifstream fin("fc.in");
    ofstream fout("fc.out");
    fin >> N;
    points = vector<Point>(N);
    int idx = 0;
    for (int i = 0; i < N; ++i) {
        fin >> points[i].x >> points[i].y;
        if (points[i].x < points[idx].x) {
            idx = i;
        } else if (abs(points[i].x - points[idx].x) <
                   std::numeric_limits<double>::epsilon() &&
                   points[i].y < points[idx].y) {
            idx = i;
        }
    }
    
    std::swap(points[idx], points[0]);
    for (int i = 1; i < N; ++i) {
        points[i].pa = (points[i].y - points[0].y) / dist(points[i], points[0]);
    }
    sort(points.begin() + 1, points.end(), [] (const Point &a, const Point &b) {
        return a.pa < b.pa;
    });
    
    double ret = graham_scan();
    cout << std::fixed << std::setprecision(2) << ret << endl;
    fout << std::fixed << std::setprecision(2) << ret << endl;
}