Cod sursa(job #1668602)

Utilizator c0mradec0mrade c0mrade Data 29 martie 2016 21:42:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<bits/stdc++.h>
#define N 125000
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct point{
    double x;
    double y;
};

point p[N],s[N];
int n,k;

double asdf(const point &p1,const point &p2,const point &p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}

bool compare(const point &p1, const point &p2)
{
    return asdf(p[1],p1,p2);
}

int main()
{
    int i,j=1;
    in>>n;
    for (i=1;i<=n;i++) {
        in>>p[i].x>>p[i].y;
        if( p[i].y<p[j].y || (p[i].y==p[j].y && p[i].x<p[j].x))
            j=i;
    }

    swap(p[1],p[j]);
    sort(p+2,p+n+1,compare);

    s[++k]=p[1];
    s[++k]=p[2];

    for (i=3;i<=n;i++) {
        while( k>=2 && asdf(s[k-1],s[k],p[i])<0 )
            k--;
        s[++k]=p[i];
    }
    out<<k<<'\n';
    for(i=1;i<=k;i++) {
        out<<setprecision(6)<<fixed<<s[i].x<<' '<<s[i].y<<'\n';
    }
    return 0;
}