Pagini recente » Cod sursa (job #2998658) | Cod sursa (job #1459241) | Cod sursa (job #567350) | Cod sursa (job #595647) | Cod sursa (job #3205923)
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#ifndef DLOCAL
#define cin fin
#define cout fout
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#endif
//#define int ll
#define double ld
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
struct Circle {
ld x, y;
ld r;
};
struct Point {
ld x, y;
};
Point eclipse(Circle a, Circle b) {
if(a.r < b.r) swap(a, b);
Point vec = Point{b.x - a.x, b.y - a.y};
vec.x /= (a.r - b.r);
vec.y /= (a.r - b.r);
return Point{b.x + vec.x * b.r, b.y + vec.y * b.r};
}
double dist(Point a, Point b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
const double eps = 1e-12;
vector<Point> convex_hull(vector<Point> v) {
sort(all(v), [&](auto a, auto b) { return a.x < b.x || (a.x == b.x && a.y > a.y); });
vector<Point> hull;
Point L = v[0], R = v.back();
auto orient = [&](Point O, Point A, Point B) { // A la stanga lui B ==> +
auto a = A.x - O.x, b = A.y - O.y, c = B.x - O.x, d = B.y - O.y;
return a * d - c * b > eps? +1 : a * d - c * b < -eps? -1 : 0;
};
hull.emplace_back(L);
for(auto x : v | views::drop(1)) {
if(orient(L, x, R) >= 0) {
while(sz(hull) >= 2 && orient(rbegin(hull)[1], rbegin(hull)[0], x) <= 0) hull.pop_back();
hull.emplace_back(x);
}
}
int dim = sz(hull) + 1;
for(auto x : v | views::reverse | views::drop(1)) {
if(orient(L, x, R) <= 0) {
while(sz(hull) >= dim + 1 && orient(rbegin(hull)[1], rbegin(hull)[0], x) <= 0) hull.pop_back();
hull.emplace_back(x);
}
}
hull.pop_back();
return hull;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n;
vector<Point> rez(n);
for(auto &[a, b] : rez) cin >> a >> b;
auto cvhull = convex_hull(rez);
reverse(all(cvhull));
double sum = 0;
cout << sz(cvhull) << '\n';
for(auto [a, b] : cvhull) cout << setprecision(12) << fixed << a << ' ' << b << '\n';
//for(int i = 0; i < sz(cvhull); i++)
//sum += dist(cvhull[i], cvhull[(i - 1 + sz(cvhull)) % sz(cvhull)]);
//cout << setprecision(18) << fixed << sum << '\n';
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/