Cod sursa(job #1593892)

Utilizator DysKodeTurturica Razvan DysKode Data 8 februarie 2016 23:00:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>
using namespace std;ifstream o("infasuratoare.in");ofstream u("infasuratoare.out");typedef pair<double,double> p;
#define x first
#define y second
#define f(a) while(k>=a+2&&s(H[k-1],H[k],v[i])<=0)k--
p v[120010],H[120010];int n,i,k,z;double s(p A,p B,p C){return((A.x*B.y+B.x*C.y+C.x*A.y)-(C.x*B.y+A.x*C.y+B.x*A.y));}int main(){o>>n;for(i=1;i<=n;i++)o>>v[i].x>>v[i].y;sort(v+1,v+n+1);for(i=1;i<=n;i++){f(0);H[++k]=v[i];}z=k;for(i=n-1;i>=1;i--){f(z-1);H[++k]=v[i];}u<<k-1<<'\n';u<<setprecision(6)<<fixed;for(i=1;i<k;i++){u<<H[i].x<<' '<<H[i].y<<'\n';}return 0;}