Cod sursa(job #965212)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 23 iunie 2013 18:07:14
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 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[100000],stak[100000];
void push(point p){stak[++vf]=p;}
void pop(){stak[vf].i=0;stak[vf--].j=0;}
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;
    }
};
void readdata()
{
    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());
}
double linie(point d1,point d2,point P)//verificam daca punctul P este deasupra sau sub dreapta d1d2
{
    return (((d1.i*d2.j) + (P.i*d1.j) + (d2.i*P.j))-((d1.i *P.j )+(d2.i * d1.j)+(P.i * d2.j)));
}
void solveHULL()
{
    point pmin=p[1],pmax=p[n];
    push(pmin);int i=2;//bagam in stiva primul pct
    while(i<n && linie(pmin,pmax,p[i])<0)++i;push(p[i]);// bag in stiva si al 2 lea punct daca exista
    ++i;
    while(i<=n)
    {
        if(linie(pmin,pmax,p[i])>=0)
        {
            push(p[i]);
            if(linie(stak[vf-2],stak[vf],stak[vf-1])<0)
            {
                pop();
                pop();
            }
            else
                ++i;
        }
        else ++i;
    }
    i-=2;
     while(i>=1)
    {
        if(linie(pmin,pmax,p[i])<=0)
        {
            push(p[i]);
            if(linie(stak[vf-2],stak[vf],stak[vf-1])<0)
            {
                pop();
                pop();
            }
            else
                --i;
        }
        else --i;
    }
    pop();

}
void print()
{
    fprintf(g,"%d\n",vf);
    while(vf)
    {
        fprintf(g,"%lf %lf\n",stak[vf].i,stak[vf].j);
        pop();
    }
}
int main()
{
    readdata();
    solveHULL();
    print();
    return 0;
}