Pagini recente » Cod sursa (job #2459134) | Cod sursa (job #2529143) | Cod sursa (job #338275) | Cod sursa (job #1955411) | Cod sursa (job #3216125)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define eb emplace_back
using ll = long long;
using ld = long double;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N = 125000 + 5;
const int Inf = 1e9;
struct P {
ld x, y;
bool operator < (const P& oth) const {
return make_pair(x,y) < make_pair(oth.x,oth.y);
}
};
P p[N];
int n, o, k;
P hull[N];
ld cross(P o, P a, P b) {
return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
bool cmp(P a, P b) {
return cross(p[1],a,b) < 0;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> p[i].x >> p[i].y;
if (!o || p[i] < p[o]) o = i;
}
swap(p[1],p[o]);
sort(p + 2, p + n + 1, cmp);
hull[1] = p[1];
hull[2] = p[2];
k=2;
for (int i = 3; i <= n; ++i) {
while (k >= 2 && cross(hull[k-1],hull[k],p[i])>0) --k;
hull[++k]=p[i];
}
fout << k << '\n';
fout << fixed << setprecision(12);
for (int i = 1; i <= k; ++i)
fout << hull[i].x << ' ' << hull[i].y << '\n';
}