Cod sursa(job #1974447)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 aprilie 2017 18:22:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

/**
 A.x A.y 1
 B.x B.y 1
 C.x C.y 1

 B.x - A.x B.y - A.y
 C.x - A.x C.y - A.y

 (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y)

*/


struct Point{
    double x,y;
    Point():x(0),y(0){};
    Point(double _x, double _y): x(_x), y(_y) {}

};

class cmp{
public:
    bool operator()(const Point &p1, const Point &p2) const {
        if(p1.x < p2.x || p1.x == p2.x && p1.y < p2.y)
            return true;
        return false;
    }
};

double det(Point A, Point B, Point C) {
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
const int Nmax = 125005;
Point Stack[Nmax];
int vf;
int N;
vector<Point> v;


int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &N);
    for(int i = 1; i <= N; ++i) {
        double x,y;
        scanf("%lf%lf", &x, &y);
        v.push_back(Point(x,y));
    }
    sort(v.begin(), v.end(), cmp());
    Point st = v[0];
    Point dr = v.back();

    Stack[++vf] = st;
    for(int i = 1; i <= N; ++i)
        if(det(st, dr, v[i]) >= 0)
        {
            while(vf >= 2 && det(Stack[vf-1], Stack[vf], v[i]) >= 0)
                --vf;
            Stack[++vf] = v[i];
        }

    for(int i = N - 1; i >= 0; --i)
        if(det(st, dr, v[i]) <= 0)
        {
            while(vf >= 2 && det(Stack[vf-1], Stack[vf], v[i]) >= 0)
                --vf;
            Stack[++vf] = v[i];
        }

    printf("%d\n", vf - 1);

    while(vf > 1) {
        printf("%.6f %.6f\n", Stack[vf].x, Stack[vf].y);
        --vf;
    }

    return 0;
}