Cod sursa(job #1320092)

Utilizator serbanSlincu Serban serban Data 17 ianuarie 2015 16:29:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

int n,poz;
double ARC,mx,D;
bool v[120050];

struct punct{
double x,y;
};
punct c[120050],p[120050],mn;

int cmp(punct XX,punct YY)
{
    if(XX.x==YY.x)
        return XX.y<YY.y;
    return XX.x<YY.x;
}

double det(int A,int B,int C)
{
    return 1;
    return c[A].x*c[B].y+c[B].x*c[C].y+c[C].x*c[A].y
        -c[A].y*c[B].x-c[B].y*c[C].x-c[C].y*c[A].x;
}

int main()
{
    int i,j;
    FILE *f=fopen("infasuratoare.in","r");
    FILE *g=fopen("infasuratoare.out","w");
    fscanf(f,"%d",&n);
    mn.y=1000000000;
    for(i=1;i<=n;i++)
        fscanf(f,"%lf%lf",&p[i].x,&p[i].y),mn.y=min(mn.y,p[i].y);
    sort(p+1,p+n+1,cmp);
    mn.x=p[1].x;
    for(i=n;i>=1;i--)
        p[i].x-=mn.x,p[i].y-=mn.y;
    c[1].x=p[1].x;c[1].y=p[1].y;
    c[2].x=p[2].x;c[2].y=p[2].y;
    v[1]=true;v[2]=true;
    int sf=2;
    for(i=3;i<n;i++)
    {
        j=1;
        while(v[j])
            j++;
        mx=atan2(c[sf].x-p[j].x,c[sf].y-p[j].y);
        poz=j;
        for(j=1;j<=n;j++)
        {
            if(!v[j])
            {
                ARC=atan2(c[sf].x-p[j].x,c[sf].y-p[j].y);
                if(ARC<mx)
                    mx=ARC,poz=j;
            }
        }
        v[poz]=true;
        sf++;
        c[sf].x=p[poz].x;
        c[sf].y=p[poz].y;
        D=det(sf-2,sf,sf-1);
        while(D<0)
        {
            sf--;
            D=det(sf-2,sf,sf-1);
        }
    }
    D=det(1,sf,sf-1);
    while(D<0)
    {
        sf--;
        D=det(1,sf,sf-1);
    }
    fprintf(g,"%d\n",sf);
    for(i=sf;i>=1;i--)
    {
        fprintf(g,"%.6f %.6f\n",c[i].x+mn.x,c[i].y+mn.y);
    }
    return 0;
}