Cod sursa(job #1320108)

Utilizator serbanSlincu Serban serban Data 17 ianuarie 2015 16:50:24
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

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

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

double det(int A,int B,int C)
{
    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;
    mn.x=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),mn.x=min(mn.x,p[i].x);
    for(i=n;i>=1;i--)
        p[i].x-=mn.x,p[i].y-=mn.y,p[i].arc=atan2(p[i].x,p[i].y);
    sort(p+1,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;
    v[1]=true;v[2]=true;
    int sf=2;
    for(i=3;i<=n;i++)
    {
        v[i]=true;
        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)
    {
        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;
}