Cod sursa(job #1593889)

Utilizator DysKodeTurturica Razvan DysKode Data 8 februarie 2016 22:53:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <bits/stdc++.h>
using namespace std;ifstream fin("infasuratoare.in");ofstream fout("infasuratoare.out");typedef pair<double,double> p;
#define x first
#define y second
#define f(a) while(k>=a+2&&sarrus(CH[k-1],CH[k],v[i])<=0)k--
p v[120010],CH[120010];int n,i,k,z;double sarrus( 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(){fin>>n;for(i=1;i<=n;i++)fin>>v[i].x>>v[i].y;sort(v+1,v+n+1);for(i=1;i<=n;i++){f(0);CH[++k]=v[i];}z=k;for(i=n-1;i>=1;i--){f(z-1);CH[++k]=v[i];}fout<<k-1<<'\n';fout<<setprecision(6)<<fixed;for(i=1;i<k;i++){fout<<CH[i].x<<' '<<CH[i].y<<'\n';}return 0;}