Pagini recente » Cod sursa (job #489086) | template/moisil-2016 | Monitorul de evaluare | Cod sursa (job #2907046) | Cod sursa (job #2753476)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
using Point = pair<double, double>;
bool CounterClockwise(const Point& a, const Point& b, const Point& c) {
auto area = a.first * b.second + b.first * c.second + a.second * c.first
- b.second * c.first - a.first * c.second - a.second * b.first;
return area > 0;
}
bool operator<(const Point& a, const Point& b) {
static constexpr double kEps = 1e-12;
if (abs(a.first - b.first) > kEps) {
return a.first < b.first;
}
return a.second < b.second;
}
vector<Point> ConvexHull(vector<Point>& points) {
auto start = *min_element(points.begin(), points.end());
sort(points.begin(), points.end(), [start](const Point& a, const Point& b) {
if (a == start || b == start) {
return a == start;
}
return CounterClockwise(start, a, b);
});
vector<Point> hull = {points[0], points[1]};
for (size_t i = 2; i < points.size(); i += 1) {
while (hull.size() > 2) {
auto a = hull[hull.size() - 2];
auto b = hull[hull.size() - 1];
if (CounterClockwise(a, b, points[i])) {
break;
}
hull.pop_back();
}
hull.push_back(points[i]);
}
return hull;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
vector<Point> points(n);
for (auto& p : points) {
fin >> p.first >> p.second;
}
auto hull = ConvexHull(points);
fout << hull.size() << "\n";
fout << fixed << setprecision(12);
for (const auto& p : hull) {
fout << p.first << " " << p.second << "\n";
}
return 0;
}