Cod sursa(job #720510)

Utilizator algotrollNume Fals algotroll Data 22 martie 2012 18:27:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

struct point
{
    double x,y;
};
typedef vector<point>::iterator v_it;

bool lower_y(point &a, point &b)
{
    if (a.y<b.y) return 1;
    else if (a.y==b.y) return a.x<b.x;
    else return 0;
}

struct lower_angle
{
    point orig;
    lower_angle(point O)
    {
        orig=O;
    }
    bool operator()(point a, point b)
    {
        a.x-=orig.x;a.y-=orig.y;
        b.x-=orig.x;b.y-=orig.y;
        return a.y*b.x<a.x*b.y;
    }
};
bool cw(point a, point b, point c)
{
    lower_angle ccw(a);
    return !ccw(b,c);
}

int main()
{
    point A,B,C;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int nP; scanf("%d",&nP);
    vector<point> vP;
    for (int i=1;i<=nP;i++)
    {
        point tmp;
        scanf("%lf%lf",&tmp.x,&tmp.y);
        vP.push_back(tmp);
    }
    v_it pTmp=min_element(vP.begin(),vP.end(),lower_y);
    point orig=*pTmp; vP.erase(pTmp);
    sort(vP.begin(),vP.end(),lower_angle(orig));

    vector<point> sol;
    sol.push_back(orig); sol.push_back(vP.front());
    for (v_it it=vP.begin()+1;it!=vP.end();++it)
    {
        while (cw(*(sol.end()-2),sol.back(),*it))
            sol.pop_back();
        sol.push_back(*it);
    }
    printf("%d\n",sol.size());
    for (int i=0;i<sol.size();i++) printf("%lf %lf\n",sol[i].x,sol[i].y);
    return 0;
}