Cod sursa(job #1668606)

Utilizator c0mradec0mrade c0mrade Data 29 martie 2016 21:48:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 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)>0;
}

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(asdf(s[k-1], s[k], p[i])<0)
            --k;
        s[++k]=p[i];
    }
    while(asdf(s[k-1], s[k], p[1])<0)
        --k;
    out<<k<<'\n';
    for(i=1;i<=k;i++) {
        out<<setprecision(12)<<fixed<<s[i].x<<' '<<s[i].y<<'\n';
    }
    return 0;
}