Cod sursa(job #720325)

Utilizator algotrollNume Fals algotroll Data 22 martie 2012 16:05:23
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 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;
    }
};

int main()
{
    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);
    v_it it=vP.begin();
    while (it!=vP.end())
    {
        point pre=sol.back();
        while (it +1!=vP.end() && !lower_angle(pre)(*it,*(it+1)))//right cw turn
            it++;
        sol.push_back(*it); 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;
}