Cod sursa(job #1411329)

Utilizator BaweeLazar Vlad Bawee Data 31 martie 2015 17:11:38
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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];
double M[4][4];
int n,i,minx,miny,k,poz=1;
int D(pct x,pct y,pct z)
{
    double X=0;
    X=(y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
    return X;
}
bool cmp(pct A,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];
    }
    for(i=k;i>=1;i--)
        fprintf(g,"%0.6f %0.6f\n",S[i].x,S[i].y);
    return 0;
}