Cod sursa(job #943278)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 24 aprilie 2013 20:09:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <stack>

#include <cstdio>
using namespace std;

const int MAX_N = 120002;

typedef struct Point{
    double x, y;
};

int N;
Point v[MAX_N], st[MAX_N];

inline double cross_product(Point a, Point b, Point c){
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}

inline bool cmp(Point a, Point b){
    return cross_product(v[1], a, b) < 0;
}

int main(){
    ifstream f("infasuratoare.in");
    freopen("infasuratoare.out", "w", stdout);

    f >> N;
    for(int i = 1; i <= N; ++i)
        f >> v[i].x >> v[i].y;

    int ind = 1;
    for(int i = 2; i <= N; ++i)
        if(v[i].x < v[ind].x)
            ind = i;
        else if(v[i].x == v[ind].x && v[i].y < v[ind].y)
            ind = i;

    Point tmp = v[1];
    v[1] = v[ind], v[ind] = tmp;

    sort(v+2, v+N+1, cmp);

    st[1] = v[1], st[2] = v[2];
    int top = 2;
    for(int i = 3; i <= N; ++i){
        while(top > 1 && cross_product(st[top-1], st[top], v[i]) > 0)
            --top;
        st[++top] = v[i];
    }

    printf("%d\n", top);
    for(int i = top; i; --i)
        printf("%.9lf %.9lf\n", st[i].x, st[i].y);

    f.close();

    return 0;
}