Cod sursa(job #1600850)

Utilizator ZanoxNonea Victor Zanox Data 15 februarie 2016 14:37:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

fstream f,g;

struct pnct
{
    double x,y;
}v[120001],stv[120001];

int n,i,j,k,l,h,h1;

int comp(pnct a,pnct b)
{
    if(a.x<b.x)return 1;
    return 0;
}

double arie(pnct a,pnct b,pnct c)
{
    return b.x*c.y+a.x*b.y+a.y*c.x-b.x*a.y-c.x*b.y-c.y*a.x;
}

int main()
{
    f.open("infasuratoare.in",ios_base::in);
    g.open("infasuratoare.out",ios_base::out);
    f>>n;
    for(i=1;i<=n;i++)f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,comp);
    h=1;
    stv[1]=v[1];
    for(i=2;i<=n;i++)
    {
        h++;
        stv[h]=v[i];
        while(arie(stv[h-2],stv[h-1],stv[h])=>0&&h>=3)
        {
            h--;
            stv[h]=stv[h+1];
        }
    }
    h1=h;
    for(i=n-1;i>=1;i--)
    {
        h++;
        stv[h]=v[i];
        while(arie(stv[h-2],stv[h-1],stv[h])=>0&&h>=2+h1)
        {
            h--;
            stv[h]=stv[h+1];
        }
    }
    g<<h-1<<'\n';
    for(i=h-1;i>=1;i--)g<<fixed<<setprecision(8)<<stv[i].x<<' '<<stv[i].y<<'\n';
}