Pagini recente » Cod sursa (job #778204) | Cod sursa (job #1287209) | Cod sursa (job #1820953) | Cod sursa (job #323491) | Cod sursa (job #1921203)
#include <bits/stdc++.h>
#define pdd pair <double, double>
#define x first
#define y second
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n, cap = 1; pdd a[120100], st[150100];
double check(pdd a, pdd b, pdd c){
return 1.00 * ((b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y));
}
bool cmp(pdd b, pdd c){
return (check(a[1], b, c) < 0);
}
int main(){
in >> n;
for(int i = 1; i <= n; i++) in >> a[i].x >> a[i].y;
sort(a+1, a+n+1);
sort(a+2, a+n+1, cmp);
st[1] = a[1];
st[2] = a[2];
cap = 2;
for(int i = 3; i <= n; i++){
while(cap >= 2 && check(st[cap-1], st[cap], a[i]) > 0) cap--;
st[++cap] = a[i];
}
out << cap << '\n';
out << fixed << setprecision(6);
for(; cap; cap--) out << st[cap].x << ' ' << st[cap].y << '\n';
return 0;
}