Cod sursa(job #1581684)

Utilizator sulzandreiandrei sulzandrei Data 27 ianuarie 2016 00:15:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define x first
#define y second
#define C(i,n) for(int i = 0 ; i < n ; i++)
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
typedef pair<double,double> P;
P v[120003],s[120003];
bool  o( P p0,P p1, P p2)
{
    return ( (p1.x - p0.x) *(p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y) >= 0);
}
void G()
{
    int p=0,t=0;
    C(i,n)
        if(v[i]<v[p])
            p = i;
   swap(v[0],v[p]);
   sort(v+1,v+n,[=](P a,P b)->bool{ return o(v[0],a,b);});
   s[0] = v[0];
   C(i,n)
   {
       while( t > 1 && !o(s[t-1],s[t],v[i]) )
           t--;
       s[++t] = v[i];
   }
   g<<t<<'\n';
   C(i,t)
       g<<setprecision(12)<<fixed<<v[i].x<<" "<<v[i].y<<'\n';
}
int main()
{
    f>>n;
    C(i,n)
        f>>v[i].x>>v[i].y;
    G();
    return 0;
}