Cod sursa(job #1540628)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 2 decembrie 2015 23:20:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,vf,poz,S[120010];
typedef pair <double, double> Tip;
Tip V[120010];
double Det(Tip a, Tip b, Tip c)
{   return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
bool cmp(Tip a, Tip b)
{   return (Det(V[1],a,b)< 0);}
int main()
{   f>>n;
    poz=1;
    for(int i=1;i<=n;i++)
    {   f>>V[i].x>>V[i].y;
        if(V[i]<V[poz]) poz = i;
    }
    swap(V[1],V[poz]);
    sort(V+2,V+n+1,cmp);
    S[++vf]=1;
    for(int i=2;i<=n;i++)
    {   while(vf>1 && Det(V[S[vf-1]],V[S[vf]],V[i])>0)
         vf--;
        S[++vf] = i;
    }
    g<<vf<<'\n';
    while(vf)
    {   g<<fixed<<setprecision(6)<<V[S[vf]].x<<' '<<V[S[vf]].y<<'\n';
        vf--;
    }
     return 0;
}