Pagini recente » Cod sursa (job #1871803) | Cod sursa (job #2446662) | Cod sursa (job #800173) | Monitorul de evaluare | Cod sursa (job #2462850)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
using Point = pair<double, double>;
constexpr double kEps = 1e-13;
bool operator<(const Point &a, const Point &b)
{
if (abs(a.first - b.first) < kEps) {
return a.second < b.second;
}
return a.first < b.first;
}
bool CounterClockwise(const Point &a, const Point &b, const Point &c)
{
return a.first * b.second + a.second * c.first + b.first * c.second
- b.second * c.first - a.first * c.second - a.second * b.first > 0;
}
Point MinPoint(const vector<Point> &points)
{
return *min_element(points.begin(), points.end());
}
vector<Point> ConvexHull(vector<Point> &points)
{
auto start = MinPoint(points);
auto cmp = [start] (const Point &a, const Point &b) {
if (a == start) {
return true;
} else if (b == start) {
return false;
}
return CounterClockwise(start, a, b);
};
sort(points.begin(), points.end(), cmp);
vector<Point> hull = {points[0], points[1]};
for (size_t i = 2; i < points.size(); i += 1) {
while (hull.size() > 1) {
auto prev1 = hull[hull.size() - 1];
auto prev2 = hull[hull.size() - 2];
if (CounterClockwise(prev2, prev1, 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";
for (const auto &p : hull) {
fout << fixed << setprecision(14) << p.first << " " << p.second << "\n";
}
return 0;
}