Cod sursa(job #1237652)

Utilizator heracleRadu Muntean heracle Data 4 octombrie 2014 15:52:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <cstdio>
#include <algorithm>

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


const int Q=120007;

int n;

struct point{
    double x,y;
} v[Q];

double clock(point a, point b, point c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int s[Q];

void make_infasurare()
{
    n++;
    v[n].x=v[1].x;
    v[n].y=v[1].y;

    s[0]=2;
    s[1]=1;
    s[2]=2;
    for(int i=3; i<=n; i++)
    {
        while(clock(v[s[s[0]-1]],v[s[s[0]]],v[i])==0)
        {
            if(v[s[s[0] ] ].x< v[s[s[0]-1]].x)
                s[0]--;
            else
            {
                v[s[s[0]-1]].x=v[s[s[0]]].x;
                v[s[s[0]-1]].y=v[s[s[0]]].y;
                s[0]--;
            }
        }

        while(clock(v[s[s[0]-1]],v[s[s[0]]],v[i])<0)
        {
            s[0]--;
        }
        s[++s[0]]=i;
    }
    s[0]--;
    n--;

    fprintf(out,"%d\n",s[0]);

    for(int i=1; i<=s[0]; i++)
    {
        fprintf(out,"%.6lf %.6lf\n",v[s[i]].x,v[s[i]].y);
    }
}

bool cmp(point a, point b)
{
    return clock(v[1],a,b)>0;
}

void find_min()
{
    int dmin=1;
    for(int i=2; i<=n; i++)
    {
        if(v[i].x==v[dmin].x && v[i].y<v[dmin].y)
            dmin=i;
        if(v[i].x<v[dmin].x)
            dmin=i;
    }
    double aux;

    aux=v[1].x;
    v[1].x=v[dmin].x;
    v[dmin].x=aux;

    aux=v[1].y;
    v[1].y=v[dmin].y;
    v[dmin].y=aux;

}

int main()
{
    fscanf(in,"%d",&n);
   // inp>>n;

    double k,q;

    for(int i=1; i<=n; i++)
    {
        if(i==241)
        {
             i+=i;
             i/=2;
        }
        //inp>>v[i].x>>v[i].y;
        //fscanf(in,"%lf %lf",&k,&q);
        fscanf(in,"%lf %lf",&v[i].x,&v[i].y);
       // v[i].x+=0.0000001;
     //   v[i].y+=0.0000001;

    }

    find_min();

    std::sort(v+2,v+n+1,cmp);

    make_infasurare();

    return 0;
}