Cod sursa(job #1829714)

Utilizator bogdi1bogdan bancuta bogdi1 Data 15 decembrie 2016 16:09:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1.e-12;
struct Point
{
    double x,y;
} v[120005];

Point LL;
int h[120005];
double cross_product(Point P1, Point P2, Point P3)
{
    return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(Point P1, Point P2, Point P3)
{
    double cp;
    cp=cross_product(P1, P2, P3);
    if(fabs(cp)<eps)
        return 0;
    else{
        if(cp>=eps)
            return 1;
        else
            return -1;
    }
}
bool cmp(Point A, Point B)
{
        int c=ccw(LL, A, B);
        if(c==1)
                return 1;
        if(c==-1)
                return 0;
}
int main()
{   freopen("infasuratoare.in", "r",stdin);
    freopen("infasuratoare.out", "w",stdout);
    int n,i,top;
    scanf("%d",&n);
    LL.x=LL.y=1000000005;
    for(i=0; i<n; i++){
            scanf("%lf%lf", &v[i].x, &v[i].y);
            if(LL.y-v[i].y>=eps)
                swap(LL,v[i]);
            else{
                if( fabs(LL.y-v[i].y)<eps)
                    if(LL.x-v[i].x>=eps)
                swap(LL,v[i]);
            }
    }
    v[0]=LL;
    sort(v+1, v+n,cmp);
    v[n]=LL;
    h[0]=0;
    h[1]=1;
    top=1;
    i=2;
    while(i<=n){
        if(ccw(v[h[top-1]], v[h[top]], v[i])>0){
            h[++top]=i;
            i++;
        }
        else
            top--;
    }
    printf("%d\n", top);
    for(i=0; i<top; i++)
        printf("%lf %lf\n", v[h[i]].x, v[h[i]].y);
    return 0;
}