Cod sursa(job #1697817)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 2 mai 2016 22:55:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

const int PMAX = 120005;
const double inf  = 1.e12;
const double eps  = 1.e-12;


struct POINT {
    double x, y;
};


POINT p[PMAX];
int   h[PMAX];


int sgn(double arg) {
    if(abs(arg)< eps) return  0;
    if(arg     < eps) return -1;
    if(arg     > eps) return +1;
}

double ccw(POINT a, POINT b, POINT c) {//2132
    return sgn((a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x));
}

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

int main(void) {
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n;
    int i, ll, top;

    ll = 0;

    scanf("%d",&n);
    for (i=0; i<n; ++i) {
        scanf("%lf %lf",&p[i].x,&p[i].y);
        if(p[ll].y < p[i].y || (p[ll].y==p[i].y && p[ll].x>p[i].y))
            ll = i;
    }

    swap(p[0], p[ll]);
    sort(p+1, p+n, cmp);
    p[n] = p[0];
    top  = 1;
    i    = 2;

    h[0] = 0;
    h[1] = 1;

    while(i<=n) {
        if(ccw(p[h[top-1]], p[h[top]], p[i])>0)
            h[++top] = i++;
        else
            --top;
    }

    printf("%d\n",top);
    for(i=0; i<=top; ++i)
        printf("%f %f\n",p[h[i]].x,p[h[i]].y);
    return 0;
}