Cod sursa(job #1397053)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 23 martie 2015 11:20:10
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.46 kb
#include<cstdio>
#include<algorithm>

FILE *fin,*fout;

struct str
{
    double x;
    double y;
    double numi;
    double numa;
} vect[120100];

int comp(str a,str b)
{
    return a.numi*b.numa<a.numa*b.numi;
}

int check(int xa,int ya,int xb,int yb,int xc,int yc)
{
    float x=xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
    //fprintf(fout,"%lf\n",x);
    if(x>0)
    {
        return 1;
    }
    return 0;
}

int q[120100];

int main()
{
    fin=fopen("infasuratoare.in","r");
    fout=fopen("infasuratoare.out","w");

    int n,p,ox=1000000000,oy=1000000000;
    fscanf(fin,"%d",&n);

    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%lf %lf",&vect[i].x,&vect[i].y);
        //fprintf(fout,"%lf %lf\n",vect[i].x,vect[i].y);
        if(ox>vect[i].x)
        {
            ox=vect[i].x;
            oy=vect[i].y;
            p=i;
        }
        else if(ox==vect[i].x)
        {
            if(oy>vect[i].y)
            {
                oy=vect[i].y;
                p=i;
            }
        }
    }

    std::swap(vect[1].x,vect[p].x);
    std::swap(vect[1].y,vect[p].y);

    for(int i=2;i<=n;i++)
    {
        vect[i].numi=vect[i].y-vect[1].y;
        vect[i].numa=vect[i].x-vect[1].x;
    }

    std::sort(vect+2,vect+n+1,comp);

    /*for(int i=1;i<=n;i++)
    {
        fprintf(fout,"%lf %lf\n",vect[i].x,vect[i].y);
    }*/

    q[0]=3;
    q[1]=1;
    q[2]=2;

    for(int i=3;i<=n;i++)
    {
        if(q[0]==2)
        {
            q[q[0]]=i;
            q[0]++;
        }
        else if(check(vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y)==1)
        {
            q[q[0]]=i;
            q[0]++;
        }
        else
        {
            //fprintf(fout,"%lf %lf    %lf %lf    %lf %lf\n",vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y);
            q[0]--;
            while(check(vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y)==0&&q[0]>=3)
            {
                q[0]--;
            }
            q[0]++;
            q[q[0]-1]=i;
            //fprintf(fout,"%lf %lf    %lf %lf    %lf %lf\n",vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y);
        }
    }
    fprintf(fout,"%d\n",q[0]-1);
    for(int i=1;i<q[0];i++)
    {
        fprintf(fout,"%lf %lf\n",vect[q[i]].x,vect[q[i]].y);
    }
}