Cod sursa(job #714885)

Utilizator ioanabIoana Bica ioanab Data 16 martie 2012 12:14:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=0.000000000001;
const int inf=1000000000;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct point
{
    double x,y;
};

point v[120005];
point s[120005];

int cmp(point a,point b)
{
    return (a.x<b.x)|| (a.x==b.x && a.y<b.y);
}

int panta(point a,point b)
{
    if(a.x-b.x<=eps && a.x-b.x>=-eps)
        return inf;
    return (a.y-b.y)/(a.x-b.x);
}
int main()
{
    int n,i,k=0;
    for(i=1;i<=n;i++)
    {
        in>>v[i].x;
        in>>v[i].y;
    }
    sort(&v[1],&v[n+1],cmp);
    s[++k]=v[1];
    s[++k]=v[n];
    for(i=2;i<n;i++)
    {
        while(abs(panta(v[i],s[k])-panta(v[i],s[k-1]))<=eps )
            k--;
        s[++k]=v[i];
    }
    for(i=n-1;i>=2;i--)
    {
        while(abs(panta(v[i],s[k])-panta(v[i],s[k-1]))<=eps )
            k--;
        s[++k]=v[i];
    }
    for(i=1;i<=k;i++)
        cout<s[i].x<<s[i].y;
    return 0;
}