Cod sursa(job #1410536)

Utilizator raduzxstefanescu radu raduzx Data 31 martie 2015 09:25:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define PI 3.14159265
using namespace std;
typedef double var;
struct puncte
{
    var x,y,panta;
};
puncte v[120003];
struct axe
{
    var x,y;
};
axe t[12000];
bool cmp(puncte a,puncte b)
{
    if(a.panta<b.panta)
        return 0;
    if(a.panta==b.panta)
        if(a.y<b.y)
            return 1;
        else
            return 0;
    return 1;
}
double determinant(axe a,axe b,puncte c)
{
    return (a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-b.x*a.y-c.y*a.x);
}
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int n,i,k=0;
    var a,b,minim=1000000010;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a>>b;
        v[i].x=a;
        v[i].y=b;
        if(v[i].x<minim) minim=v[i].x;
    }
    if(minim<0)
    {
        for(i=1;i<=n;i++)
        {
            v[i].x+=minim;
            v[i].panta=atan2(v[i].y,v[i].x);
        }
    }
    else
        for(i=1;i<=n;i++)
        {
            v[i].panta=atan2(v[i].y,v[i].x);
        }
    sort(v+1,v+n+1,cmp);

    t[1].x=v[1].x;
    t[1].y=v[1].y;
    t[2].y=v[2].y;
    t[2].x=v[2].x;
    k=2;
    int j;
    for(i=3;i<=n;i++)
    {
        if(determinant(t[k-1],t[k],v[i])<0)
        {
            k+=1;
            t[k].x=v[i].x;
            t[k].y=v[i].y;
        }
        else
        {
            t[k].x=v[i].x;
            t[k].y=v[i].y;
        }
    }
    g<<k<<'\n';
    if(minim<0)
        for(i=k;i>=1;i--)
        {
            g<<setprecision(6)<<fixed<<t[i].x-minim<<" "<<t[i].y<<'\n';
        }
    else
        for(i=k;i>=1;i--)
        {
            g<<setprecision(6)<<fixed<<t[i].x<<" "<<t[i].y<<'\n';
        }
    f.close();
    g.close();
    return 0;
}