Pagini recente » Cod sursa (job #3324604) | Borderou de evaluare (job #3331984) | Cod sursa (job #3306758) | Cod sursa (job #3356153) | Cod sursa (job #3338645)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define double ld
const int NMAX = 1.2e5+5;
struct Point {
double x, y;
};
int n;
Point a[NMAX];
set<pair<double, double>> s;
int dist(const Point &a, const Point &b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int det(const Point &a, const Point &b, const Point &c) {
// return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
void read() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
if (s.count({ a[i].x, a[i].y })) {
i--;
n--;
} else {
s.emplace(a[i].x, a[i].y);
}
}
}
void solve() {
a[0] = a[1];
for (int i = 2; i <= n; i++) {
if (a[i].y < a[0].y || (a[i].y == a[0].y && a[i].x < a[0].x)) {
a[0] = a[i];
}
}
sort(a + 1, a + n + 1, [&](const Point &p1, const Point &p2) {
int d = det(a[0], p1, p2);
return d < 0;
if (d == 0) return dist(a[0], p1) < dist(a[0], p2);
return d < 0;
});
vector<Point> hull = { a[1], a[2] };
for (int i = 3; i <= n; i++) {
while (hull.size() > 1 && det(hull[hull.size() - 2], hull.back(), a[i]) > 0) {
hull.pop_back();
}
hull.push_back(a[i]);
}
reverse(hull.begin(), hull.end());
cout << hull.size() << endl;
for (auto [ x, y ] : hull) {
cout << setprecision(12) << fixed << x << ' ' << y << '\n';
}
#if 0
n = hull.size();
int ans = 0;
for (int i = 0, j = 0; i < n; i++) {
ans = max(ans, dist(hull[i], hull[j]));
while (dist(hull[i], hull[j]) < dist(hull[i], hull[(j + 1) % n])) {
j = (j + 1) % n;
ans = max(ans, dist(hull[i], hull[j]));
}
for (int k = -500; k <= 500; k++) {
ans = max(ans, dist(hull[i], hull[(j + k + 1000ll * n) % n]));
}
}
return sqrtl(ans);
#endif
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#else
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
read();
solve();
return 0;
}