Cod sursa(job #1343995)

Utilizator horiainfoTurcuman Horia horiainfo Data 16 februarie 2015 10:10:18
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1 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;
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=poz;i>=1;i--)
    {
        fout.precision(6);
        fout<<fixed<<p[v[i]].x<<' '<<fixed<<p[v[i]].y<<'\n';
    }
}
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; v[2]=2; used[2]=true; poz=2; pas=1;
    while(v[poz]!=1)
    {
        int k=v[poz]+pas;
        while(pozitie(p[v[poz-1]],p[v[poz]],p[k])>0)
            poz--;
        v[++poz]=k;
        if(v[poz]==nrp) pas=-1;
    }
    afis(poz-1);
    return 0;
}