Pagini recente » Istoria paginii utilizator/bulbfan | Monitorul de evaluare | Istoria paginii utilizator/silentstrike | Monitorul de evaluare | Cod sursa (job #1921000)
#include <bits/stdc++.h>
using namespace std;
//MACROS
#define X first
#define Y second
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef pair <double, double> PDD;
double cww(PDD a1, PDD a2, PDD a3) { return (a1.X - a2.X) * (a1.Y - a3.Y) - (a1.X - a3.X) * (a1.Y - a2.Y); }
PDD a[120120], st[120120];
int main() {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
//freopen("in.txt","r",stdin);
int n, idx = 0;
cin >> n;
rep(i,0,n) {
cin >> a[i].X >> a[i].Y;
if (a[idx] > a[i]) idx = i;
}
swap(a[idx],a[0]);
sort(a+1,a+n,[&](PDD v, PDD u) { return cww(a[0],v,u) < 0; });
int sz = 1;
st[0] = a[0], st[1] = a[1];
rep(i,2,n) {
while (sz && cww(st[sz-1],st[sz],a[i]) > 0) sz--;
st[++sz] = a[i];
}
cout << sz+1 << "\n";
while (sz >= 0) printf("%.10f %.10f\n",st[sz].X,st[sz].Y), sz--;
}