Cod sursa(job #1410573)

Utilizator raduzxstefanescu radu raduzx Data 31 martie 2015 09:59:08
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 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;
    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)*180/PI;
        }
    }
    else
        for(i=1;i<=n;i++)
        {
            v[i].panta=atan2(v[i].y,v[i].x)*180/PI;
        }
    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++)
    {
        while(determinant(t[k-1],t[k],v[i])>0)
            k--;

            k+=1;
            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;
}