Cod sursa(job #967197)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 iunie 2013 12:35:22
Problema Infasuratoare convexa Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <cstdio>
#include <algorithm>
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
using namespace std;
int n,vf;
struct point{double i,j;}p[120010],stak[120010];
struct cmp{bool operator()(const point p1,const point p2)const{if(p1.i<p2.i)return 1;if(p1.i==p2.i && p1.j<p2.j)return 1;return 0;}};
double side(point d1,point d2,point P){return d1.i*d2.j+d2.i*P.j+P.i*d1.j-P.j*d1.i-d1.j*d2.i-d2.j*P.i;}
void push(point p){stak[++vf].i=p.i,stak[vf].j=p.j;}
void pop(){stak[vf].i=0;stak[vf--].j=0;}
void prepare()
{
    fscanf(f,"%d",&n);
    for(int i=1;i<=n;++i)fscanf(f,"%lf%lf",&p[i].i,&p[i].j);
    sort(p+1,p+n+1,cmp());
}
void make_hull()
{
    int i=2;
    point pmin,pmax;
    pmin=p[1];pmax=p[n];
    push(pmin);
    while(i<n && side(pmin,pmax,p[i])<0)++i;
    if(i<n)push(p[i]);++i;
    while(i<n)
    {
        if(side(pmin,pmax,p[i])>0)
        {
            push(p[i]);
            if(side(stak[vf-2],stak[vf],stak[vf-1])<0)
                pop(),pop();
            else ++i;
        }
        else ++i;
    }
    push(pmax);
    while(vf>=2){if(side(stak[vf-2],stak[vf],stak[vf-1])<0){pop();pop();push(pmax);}else break;}
    --i;
    while(i>=1)
    {
        if(side(pmin,pmax,p[i])<=0)
        {
            push(p[i]);
                if(side(stak[vf-2],stak[vf],stak[vf-1])<0)
                pop(),pop();
            else --i;
        }
        else --i;
    }
    pop();
}
void print_hull()
{
    fprintf(g,"%d\n",vf);
    fprintf(g,"%lf %lf\n",stak[1].i,stak[1].j);
    while(vf>1)fprintf(g,"%lf %lf\n",stak[vf].i,stak[vf].j),pop();
}
int main()
{
    prepare();
    make_hull();
    print_hull();
    return 0;
}