Pagini recente » Cod sursa (job #2987550) | Cod sursa (job #169851) | Cod sursa (job #1346598) | Cod sursa (job #2687839) | Cod sursa (job #2477560)
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define ld double
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n, vf;
pair<ld, ld> pts[120100];
pair<ld, ld> conv[120100];
ld delta(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> c) {
return (a.fi * b.se + b.fi * c.se + c.fi * a.se - a.se * b.fi - b.se * c.fi - c.se * a.fi);
}
bool cmp(pair<ld, ld> a, pair<ld, ld> b) {
return delta(conv[1], a, b) < 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
in >> n;
for (int i = 1; i <= n; i++)
in >> pts[i].fi >> pts[i].se;
sort(pts + 1, pts + n + 1);
conv[++vf] = pts[1];
sort(pts + 2, pts + n + 1, cmp);
conv[++vf] = pts[2];
for (int i = 3; i <= n; i++) {
while (vf > 2 && delta(conv[vf - 1], conv[vf], pts[i]) > 0)
vf--;
conv[++vf] = pts[i];
}
out << vf << '\n';
while (vf--)
out << conv[vf + 1].fi << ' ' << conv[vf + 1].se << '\n';
return 0;
}