Cod sursa(job #1645767)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 10 martie 2016 13:40:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#define Point pair<double,double>
#define x first
#define y second
#define N 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
Point v[N],stac[N];
int head,n;
void read()
{
    fin>>n;
    for(int i=1;i<=n;i++) fin>>v[i].x>>v[i].y;
}
inline double produs_incrucisat(const Point & A,const Point& B,const Point& C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline int cmp(const Point& p1,const Point& p2)
{
    return produs_incrucisat(v[1],p1,p2)<0;
}
void sort_points()
{
    int pos=1;
    for(int i=1;i<=n;i++) if(v[i]<v[pos]) pos=i;
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,cmp);
}
void convex_hull()
{
    sort_points();
    stac[1]=v[1];
    stac[2]=v[2];
    head=2;
    for(int i=3;i<=n;i++)
    {
        while(head>=2 && produs_incrucisat(stac[head-1],stac[head],v[i])>0) --head;
        stac[++head]=v[i];
    }
}
void write()
{
    fout<<fixed;
    fout<<head<<"\n";
    for(int i=head;i>=1;i--)
    {
        fout<<setprecision(9)<<stac[i].x<<" "<<stac[i].y<<"\n";
    }
}
int main()
{
    read();
    convex_hull();
    write();
}