Cod sursa(job #1040975)

Utilizator andreiiiiPopa Andrei andreiiii Data 25 noiembrie 2013 12:03:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <algorithm>
#include <bitset>
#include <fstream>
#define N 120002
#define EPS 1e-12
#define pc pair<double, double>
#define x first
#define y second
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

pc a[N];
bitset <N> v;
int inf[N];

double sarr(pc o, pc a, pc b)
{
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}

int main()
{
    int n, i, sign=1;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
    }
    sort(a+1, a+n+1);
    v[2]=1;
    inf[1]=1;inf[2]=2;inf[0]=2;
    for(i=1;i;i+=sign)
    {
        if(!v[i])
        {
            while(inf[0]>1&&sarr(a[inf[inf[0]-1]], a[inf[inf[0]]], a[i])<EPS)
            {
                v[inf[inf[0]--]]=0;
            }
            inf[++inf[0]]=i;
            v[i]=1;
        }
        if(i==n) sign=-1;
    }
    fout<<inf[0]-1<<"\n";
    fout.precision(6);
    fout<<fixed;
    for(i=1;i<inf[0];i++)
    {
        fout<<a[inf[i]].x<<" "<<a[inf[i]].y<<"\n";
    }
}