Cod sursa(job #1320419)

Utilizator serbanSlincu Serban serban Data 17 ianuarie 2015 22:59:29
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

int n,poz;
double ARC,mx,D;

struct puncte{
double x,y,arc;
};
struct punct{
double x,y;
};
punct c[120050],p[120050],mn,aux;
/*
int cmp(puncte XX,puncte YY)
{
    if(XX.arc==YY.arc)
    {
        if(XX.x==0)
        {
            return XX.y>YY.y;
        }
        else if(XX.x==YY.x)
            return XX.y<YY.y;
        return XX.x<YY.x;
    }
    return XX.arc<YY.arc;
}
*/
double det(punct A,punct B,punct C)
{
    return (A.x-B.x)*(C.y-B.y)-(A.y-B.y)*(C.x-B.x);
}
bool cmp(punct a,punct b)
{
    return (det(a,mn,b)>0);
}


int main()
{
    int i,j;
    FILE *f=fopen("infasuratoare.in","r");
    FILE *g=fopen("infasuratoare.out","w");
    fscanf(f,"%d",&n);
    mn.y=1000000000;
    mn.x=1000000000;
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%lf%lf",&p[i].x,&p[i].y);
        if(mn.x>p[i].x)
        {
            mn.x=p[i].x;
            mn.y=p[i].y;
            j=i;
        }
        else if(mn.x==p[i].x)
            if(p[i].y<mn.y)
                mn.y=p[i].y,j=i;
    }/*
    for(i=n;i>=1;i--)
    {
        p[i].x-=mn.x;
        p[i].y-=mn.y;
        if(p[i].x==0 && p[i].y==0) j=i;
    }*/
    aux=p[j];
    p[j]=p[1];
    p[1]=aux;
    //for(i=1;i<=n;i++)
    //    p[i].arc=atan2(p[i].x,p[i].y);
    sort(p+2,p+n+1,cmp);
    c[1].x=p[1].x;c[1].y=p[1].y;
    c[2].x=p[2].x;c[2].y=p[2].y;
    int sf=3;
    for(i=3;i<=n;i++)
    {
        while(sf>0)
        {
            c[0].x=p[i].x;
            c[0].y=p[i].y;
            if(det(c[sf-1],c[sf],c[0])>=0)
                sf--;
            else
                break;
        }
        sf++;
        c[sf].x=p[i].x;
        c[sf].y=p[i].y;
    }

    /*for(i=3;i<=n;i++)
    {
        sf++;
        c[sf].x=p[i].x;
        c[sf].y=p[i].y;
        D=det(sf-2,sf,sf-1);
        while(D<0)
        {
            c[sf-1].x=c[sf].x;
            c[sf-1].y=c[sf].y;
            sf--;
            D=det(sf-2,sf,sf-1);
        }
    }
    D=det(1,sf,sf-1);
    while(D<0)
    {
        c[sf-1].x=c[sf].x;
        c[sf-1].y=c[sf].y;
        sf--;
        D=det(1,sf,sf-1);
    }*/
    fprintf(g,"%d\n",sf);
    for(i=2;i<=sf;i++)
    {
        fprintf(g,"%.6f %.6f\n",c[i].x,c[i].y);
    }
    fprintf(g,"%.6f %.6f\n",c[1].x,c[1].y);
    return 0;
}