Cod sursa(job #929331)

Utilizator tudy23Coder Coder tudy23 Data 26 martie 2013 23:09:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <deque>
#include <cmath>
#define mp make_pair
#define pb push_back
#define pf push_front
#define x first
#define y second
using namespace std;
const double prec=(pow(10,-12));
int n;
deque <pair<double,double> > ic;    //inf convexa
inline double stanga(pair<double,double> p0, pair<double,double> p1, pair<double,double> p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
}
void citire()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    double xx,yy;
    pair<double,double> p[3];
    for(int i=0;i<3;++i)
    {
        scanf("%lf%lf",&xx,&yy);
        p[i]=mp(xx,yy);
    }
    if(stanga(p[0],p[1],p[2])>prec)
    {
        ic.pb(p[0]);
        ic.pb(p[1]);
    }
    else
    {
        ic.pb(p[1]);
        ic.pb(p[0]);
    }
    ic.pb(p[2]);
    ic.pf(p[2]);
    for(int i=3;i<n;++i)
    {
        scanf("%lf%lf",&xx,&yy);
        p[0]=mp(xx,yy);
        if(stanga(ic.back(),ic[ic.size()-2],p[0])>prec&&stanga(ic[1],ic.front(),p[0])>prec)
            continue; // este in interiorul poligonului;
        while(stanga(ic[ic.size()-2],ic.back(),p[0])<=prec)
            ic.pop_back();
        ic.pb(p[0]);
        while(stanga(ic.front(),ic[1],p[0])<=prec)
            ic.pop_front();
        ic.pf(p[0]);
    }
    fclose(stdin);
    freopen("infasuratoare.out","w",stdout);
    for(int i=0;i<ic.size()-1;++i)
        printf("%lf %lf\n",ic[i].x,ic[i].y);
    fclose(stdout);
}
int main()
{
    citire();
    return 0;
}