Cod sursa(job #1738743)

Utilizator mihai.alphamihai craciun mihai.alpha Data 7 august 2016 16:24:08
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.89 kb
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;

class Point    {
public:
    double x, y;

    // comparison is done first on y coordinate and then on x coordinate
    bool operator < (Point b) {
        if (y != b.y)
            return y < b.y;
        return x < b.x;
    }
};

// Point having the least y coordinate, used for sorting other points
// according to polar angle about this point
Point pivot;

// returns -1 if a -> b -> c forms a counter-clockwise turn,
// +1 for a clockwise turn, 0 if they are collinear
int ccw(Point a, Point b, Point c) {
    int area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (area > 0)
        return -1;
    else if (area < 0)
        return 1;
    return 0;
}

// returns square of Euclidean distance between two points
int sqrDist(Point a, Point b)  {
    int dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

// used for sorting points according to polar order w.r.t the pivot
bool POLAR_ORDER(Point a, Point b)  {
    int order = ccw(pivot, a, b);
    if (order == 0)
        return sqrDist(pivot, a) < sqrDist(pivot, b);
    return (order == -1);
}

stack<Point> grahamScan(Point *points, int N)    {
    stack<Point> hull;

    if (N < 3)
        return hull;

    // find the point having the least y coordinate (pivot),
    // ties are broken in favor of lower x coordinate
    int leastY = 0;
    for (int i = 1; i < N; i++)
        if (points[i] < points[leastY])
            leastY = i;

    // swap the pivot with the first point
    Point temp = points[0];
    points[0] = points[leastY];
    points[leastY] = temp;

    // sort the remaining point according to polar order about the pivot
    pivot = points[0];
    sort(points + 1, points + N, POLAR_ORDER);

    hull.push(points[0]);
    hull.push(points[1]);
    hull.push(points[2]);

    for (int i = 3; i < N; i++) {
        Point top = hull.top();
        hull.pop();
        while (ccw(hull.top(), top, points[i]) != -1)   {
            top = hull.top();
            hull.pop();
        }
        hull.push(top);
        hull.push(points[i]);
    }
    return hull;
}
Point points[100300];
double px[100300], py[100300];int nr;
int main()  {
    int n;
    int i;
    FILE *fin = fopen("infasuratoare.in", "r"), *fout = fopen("infasuratoare.out", "w");
    fscanf(fin, "%d", &n);
    for(i = 0;i < n;i++)  {
        fscanf(fin, "%lf%lf", &points[i].x, &points[i].y);
    }
    stack<Point> hull = grahamScan(points, n);
    while (!hull.empty())   {
        Point p = hull.top();
        hull.pop();
        px[nr] = p.x;
        py[nr] = p.y;
       // printf("%lf %lf\n", p.x, p.y);
        nr++;
    }
    fprintf(fout, "%d\n", nr);
    for(i = nr - 1;i >= 0;i--)
        fprintf(fout, "%lf %lf\n", px[i], py[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}