Cod sursa(job #1344936)

Utilizator horiainfoTurcuman Horia horiainfo Data 17 februarie 2015 08:59:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{double x,y;} p[120001];
int nrp,v[120001],ok,pas,poz,k;
bool used[120001];
double pozitie(point A,point B,point C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-A.x*C.y-B.x*A.y;
}
bool test(point A,point B)
{
    if(A.x!=B.x)
        return A.x<B.x;
    else
        return A.y<B.y;
}
void afis(int poz)
{
    fout<<poz<<'\n';
    for(int i=1;i<=poz;i++)
    {
        fout.precision(6);
        fout<<fixed<<p[v[i]].x<<' '<<fixed<<p[v[i]].y<<'\n';
    }
}
int poligon()
{
    int k;
    while(v[poz]!=1)
    {
        k=v[poz]+pas;
        while(used[k]==true) k=k+pas;
        while(pozitie(p[v[poz-1]],p[v[poz]],p[k])<=0 && poz>=2)
            used[v[poz]]=false,poz--;
        if(poz==1) return 0;
        v[++poz]=k; used[k]=true;
        if(k==nrp) pas=-pas;
    }
    return 1;
}
int main()
{
    fin>>nrp;
    for(int i=1;i<=nrp;i++)
        fin>>p[i].x>>p[i].y;
    sort(p+1,p+nrp+1,test);
    v[1]=1;
    for(int i=2;i<=nrp;i++)
    {
        poz=2; pas=1;
        v[2]=i; used[i]=true;
        if(poligon()==1) break;
        used[i]=false;
    }
    afis(poz-1);
    return 0;
}