Pagini recente » Cod sursa (job #966470) | Cod sursa (job #1238081) | Cod sursa (job #264216) | Cod sursa (job #3001566) | Cod sursa (job #2223403)
/// Graham
#include <bits/stdc++.h>
#define x first
#define y second
#define rev(v) (v.rbegin())
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
using f64 = double;
using ptx = pair<f64, f64>;
const f64 EPS = 1e-12;
vector<ptx> v, hull;
int n;
static f64 det(const ptx &c, const ptx &a, const ptx &b) {
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x); }
static int orient(const ptx &c, const ptx &b, const ptx &a) {
f64 d = det(c, a, b);
if (abs(d) < EPS)
return 0;
return d > 0 ? 1 : -1; }
static f64 norm(const ptx &a, const ptx &b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }
int main() {
fi >> n;
v.resize(n);
hull.reserve(n);
for (auto &i: v)
fi >> i.x >> i.y;
swap(*min_element(begin(v), end(v)), v[0]);
hull.push_back(v[0]);
sort(begin(v) + 1, end(v), [&](const ptx &a, const ptx &b) {
return orient(v[0], a, b) == 0 ? norm(v[0], a) < norm(v[0], b) : orient(v[0], a, b) < 0; });
for (int i = 1; i < n; ++i) {
while (hull.size() > 2 && orient(rev(hull)[0], rev(hull)[1], v[i]) <= 0)
hull.pop_back();
hull.push_back(v[i]); }
fo << setprecision(6) << fixed;
fo << hull.size() << '\n';
for (auto i: hull)
fo << i.x << ' ' << i.y << '\n';
return 0; }