Cod sursa(job #1110815)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 18 februarie 2014 13:34:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <iomanip>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<double,double> point;

FILE *f = fopen("infasuratoare.in","r");
FILE *g = fopen("infasuratoare.out","w");

int n, i, p;

int s[120005],h;

point v[120005], tmp;

int det(const point &a, const point &b, const point &c) {
    if( (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) > 0)
        return -1;
    else
        return 1;
}

bool cmp(const point &a, const point &b) {
    if(det(v[1],a,b)==-1)
        return 1;
    return 0;
}

int main() {
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
    p=1;
    for(i=2;i<=n;i++)
        if(v[i].y<v[p].y || (v[i].x==v[p].x && v[i].x<v[p].x) )
            p=i;
    tmp=v[p];
    v[p]=v[1];
    v[1]=tmp;
    sort(v+2,v+n+1,cmp);
    s[1]=1;
    s[2]=2;
    h=2;
    for(i=3;i<=n;i++) {
        while(h>=2 && det(v[s[h-1]],v[s[h]],v[i])==1)
            h--;
        s[++h]=i;
    }

    fprintf(g,"%d\n",h);

    for(i=1;i<=h;i++)
        fprintf(g,"%.6lf %.6lf\n", v[s[i]].x,v[s[i]].y);

    return 0;
}