Pagini recente » Cod sursa (job #358523) | Cod sursa (job #2373682) | Cod sursa (job #1688011) | Cod sursa (job #1416642) | Cod sursa (job #2700309)
#include <bits/stdc++.h>
using namespace std;
using Point = complex<double>;
using Poly = vector<Point>;
const double EPS = 1e-12;
double cross(Point a, Point b) {
return a.real() * b.imag() - a.imag() * b.real();
}
double det(Point a, Point b, Point c) {
return cross(b - a, c - a);
}
namespace std {
bool operator<(const Point a, const Point b) {
return make_pair(a.real(), a.imag()) <
make_pair(b.real(), b.imag());
}
}
Poly HullHalf(Poly& P, int z) {
Poly ret;
for (auto p : P) {
while ((int)ret.size() >= 2 &&
z * det(ret.end()[-2], ret.end()[-1], p) < EPS)
ret.pop_back();
ret.push_back(p);
}
return ret;
}
Poly Hull(Poly P) {
sort(P.begin(), P.end());
P.erase(unique(P.begin(), P.end()), P.end());
auto l = HullHalf(P, +1), u = HullHalf(P, -1);
l.insert(l.end(), u.rbegin() + 1, u.rend() - 1);
return l;
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n; cin >> n;
vector<Point> P;
for (int i = 0; i < n; ++i) {
double x, y; cin >> x >> y;
P.emplace_back(x, y);
}
auto H = Hull(P);
cout << fixed << setprecision(12);
cout << H.size() << '\n';
for (auto p : H)
cout << p.real() << " " << p.imag() << '\n';
return 0;
}