Cod sursa(job #1038232)

Utilizator smaraldaSmaranda Dinu smaralda Data 21 noiembrie 2013 11:03:25
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;

const double eps = 1.e-14;

struct POINT {
    double x,y;
    POINT (double x=0, double y=0) {
        this -> x = x;
        this -> y = y;
    }
};
vector <POINT> p,st;

int ccw (POINT P1, POINT P2, POINT P3) {
    double cp = (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
    if(cp < 0)
        return -1;
    if(cp > 0)
        return 1;
    return 0;
}

class cmp {
    public:
        bool operator () (POINT a, POINT b) {
            return ccw(p[0],a,b) > 0;
        }
};

int main() {
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int i,n;
    double x,y;

    scanf("%d",&n);
    for(i = 0; i < n; i++) {
        scanf("%lf%lf",&x,&y);
        p.push_back(POINT(x,y));
    }

    for(i = 1; i < n; i++)
        if(p[i].x < p[0].x || (fabs(p[i].x - p[0].x) < eps && p[i].y < p[0].y))
            swap(p[i],p[0]);

    sort(p.begin(),p.end(),cmp());
    p.push_back(p[0]);

    i = 0;
    while(i < p.size()) {
        if(st.size() < 2 || ccw(st[st.size() - 2],st[st.size() - 1],p[i]) > 0) {
            st.push_back(p[i]);
            i++;
        }
        else
            st.erase(st.end() - 1);
    }

    printf("%d\n",st.size());
    for(i = 1; i < st.size(); i++) {
        printf("%lf %lf\n",st[i].x,st[i].y);
    }
    return 0;
}