Cod sursa(job #1411353)

Utilizator BaweeLazar Vlad Bawee Data 31 martie 2015 17:25:18
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
typedef pair<double, double> pct;
pct p[120005],S[120005];
int n,i,minx,miny,k,poz=1;
int D(const pct& x,const pct& y,const pct& z)
{
    return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
}
bool cmp(const pct& A,const pct& B)
{
    return D(p[1],A,B)<0;
}
int main()
{
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%lf %lf\n",&p[i].x,&p[i].y);
    for(i=2;i<=n;i++)
        if(p[i]<p[poz])
            poz=i;
    swap(p[1],p[poz]);
    sort(p+2,p+n+1,cmp);
    S[1]=p[1];
    S[2]=p[2];
    k=2;
    for(i=3;i<=n;i++)
    {
        while(k>=2 and D(S[k-1],S[k],p[i])>0)
            --k;
        S[++k]=p[i];
    }
    fprintf(g,"%d\n",k);
    for(i=k;i>=1;i--)
        fprintf(g,"%0.9f %0.9f\n",S[i].x,S[i].y);
    return 0;
}