Pagini recente » Cod sursa (job #72814) | Cod sursa (job #1128151) | Cod sursa (job #722802) | Cod sursa (job #608917) | Cod sursa (job #2267828)
#include <bits/stdc++.h>
#define ll long long
#define pdd pair < double, double >
using namespace std;
int n, vf;
pdd a[120100], st[120100];
int check(pdd a, pdd b, pdd c){
return 1.0 * ((b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second));
}
bool cmp(pdd b, pdd c){
return check(a[1], b, c) < 0;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> a[i].first >> a[i].second;
}
sort(a + 1, a + n + 1);
sort(a + 2, a + n + 1, cmp);
st[++vf] = a[1];
st[++vf] = a[2];
for (int i = 3; i <= n; i++){
while (vf >= 2 && check(st[vf - 1], st[vf], a[i]) > 0) --vf;
st[++vf] = a[i];
}
cout << vf << "\n";
cout << fixed << setprecision(6);
for (; vf; vf--){
cout << st[vf].first << " " << st[vf].second << "\n";
}
return 0;
}