UVa 681

uva_681.cpp

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

using namespace std;

const double eps = 1e-8;

int cmp(double x) {
    if (fabs(x) < eps) return 0;
    if (x > 0) return 1;
    return -1;
}

struct Point {
    double x, y;
    Point() {}
    Point(double a, double b): x(a), y(b) {}
    Point operator-(const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
    bool operator==(const Point &rhs) const {
        return cmp(x - rhs.x) == 0 && cmp(y - rhs.y) == 0;
    }
};

class Solver {
public:
    Solver(const vector<Point> &P): points(P) {}
    void run(void);
private:
	double cross(const Point &O, const Point &A, const Point &B)
	{
		return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
	}
    void ComputeConvexHull(void);
    vector<Point> points;
};

bool ComparePoints(const Point &a, const Point &b)
{
    return cmp(a.y - b.y) < 0 || (cmp(a.y - b.y) == 0 && a.x < b.x);
}

void Solver::ComputeConvexHull()
{
	int n = points.size();
    vector<Point> convex_hull(2 * n);

    sort(points.begin(), points.end(), ComparePoints);
    points.erase(unique(points.begin(), points.end()), points.end());

    int k = 0;
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(convex_hull[k - 2],
        					   convex_hull[k - 1],
        					   points[i]) <= eps)
        	--k;
        convex_hull[k++] = points[i];
    }

    int t = k + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (k >= t && cross(convex_hull[k - 2],
        	                   convex_hull[k - 1],
        	                   points[i]) <= eps)
        	--k;
        convex_hull[k++] = points[i];
    }

    points.assign(convex_hull.begin(), convex_hull.begin() + k);
}

void Solver::run()
{
	ComputeConvexHull();

	printf("%lu\n", points.size());
	for (int i = 0; i < points.size(); ++i)
		printf("%d %d\n", static_cast<int>(points[i].x),
			              static_cast<int>(points[i].y));
}

int main()
{
    int K, N;
    scanf("%d", &K);
    printf("%d\n", K);
    for (int i = 1; i <= K; ++i) {
        scanf("%d", &N);
        vector<Point> p;
        double x, y;
        for (int j = 0; j < N - 1; ++j) {
            scanf("%lf%lf", &x, &y);
            p.push_back(Point(x, y));
        }
        scanf("%*lf%*lf");
        if (i != K)
            scanf("%*d");
        Solver s(p);
        s.run();
        if (i != K)
            puts("-1");
    }
}