Cod sursa(job #1581697)

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