Pagini recente » Cod sursa (job #3205923) | Cod sursa (job #3141419) | Borderou de evaluare (job #567874) | Cod sursa (job #1945467) | Cod sursa (job #3205913)
#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> upper, lower;
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;
};
upper.emplace_back(L);
lower.emplace_back(L);
for(auto x : v | views::drop(1) | views::take(sz(v) - 2)) {
if(orient(L, x, R) == +1)
lower.emplace_back(x);
else
upper.emplace_back(x);
}
lower.emplace_back(R);
upper.emplace_back(R);
auto mkst = [&orient](vector<Point> lst) {
vector<Point> st;
st.emplace_back(lst[0]);
for(auto x : lst | views::drop(1)) {
while(sz(st) >= 2 && orient(rbegin(st)[1], rbegin(st)[0], x) >= 0) st.pop_back();
st.emplace_back(x);
}
st.pop_back();
return st;
};
auto pesus = mkst(upper);
//for(auto [a, b] : pesus) cerr << a << ' ' << b << '\t'; cerr << '\n';
reverse(all(lower));
auto pejos = mkst(lower);
//for(auto [a, b] : pejos) cerr << a << ' ' << b << '\t'; cerr << '\n';
copy(all(pejos), back_inserter(pesus));
return pesus;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n;
cin >> n;
//vector<Circle> circ(n);
//for(auto &[x, y, r] : circ) {
//cin >> x >> y >> r;
//}
//sort(all(circ), [&](auto a, auto b) { return a.r < b.r; });
vector<Point> rez(n);
for(auto &[a, b] : rez) cin >> a >> b;
//for(int i = 1; i < sz(circ); i++)
//rez.emplace_back(eclipse(circ[i], circ[i - 1]));
auto cvhull = convex_hull(rez);
//cerr << "--\n";
//for(auto [a, b] : cvhull) cerr << a << ' ' << b << '\n';
//cerr << "--\n";
//double sum = 0;
reverse(all(cvhull));
//for(int i = 0; i < sz(cvhull); i++)
//sum += dist(cvhull[i], cvhull[(i - 1 + sz(cvhull)) % sz(cvhull)]);
cout << sz(cvhull) << '\n';
//cerr << "--\n";
for(auto [x, y] : cvhull) cout << setprecision(12) << fixed << x << ' ' << y << '\n';
//cout << setprecision(18) << fixed << sum << '\n';
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/