Cod sursa(job #1334388)

Utilizator rsteliRadu Stelian rsteli Data 4 februarie 2015 12:38:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

#define nmax 120010

int n,poz,varf;
struct point
{
    double x,y;
}v[nmax],st[nmax];

double prod(point p1,point p2,point p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}

int comp(point p1,point p2)
{
    return prod(v[1],p1,p2)<0;
}

int main()
{
    int i,j;
    cin>>n;
    cin>>v[1].x>>v[1].y;
    poz=1;
    for (i=2;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
        if (v[i].x<v[poz].x)
            poz=i;
        else if (v[i].x==v[poz].x && v[i].y<v[poz].y)
            poz=i;
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,comp);
    st[1]=v[1];
    st[2]=v[2];
    varf=2;
    for (i=3;i<=n;i++)
    {
        while (varf>=2 && prod(st[varf-1],st[varf],v[i])>0)
            varf--;
        st[++varf]=v[i];
    }
    cout<<fixed;
    cout<<varf<<'\n';
    for (i=varf;i;i--)
        cout<<setprecision(12)<<st[i].x<<" "<<st[i].y<<'\n';
}