Pagini recente » Cod sursa (job #1010573) | Cod sursa (job #2069326) | Cod sursa (job #3156959) | Cod sursa (job #1075894) | Cod sursa (job #2032931)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
const double kEps = 1e-12;
const double kInf = 1e12;
struct Point
{
double x, y;
bool operator==(const Point &other) const
{
return abs(x - other.x) < kEps && abs(y - other.y) < kEps;
}
bool operator<(const Point &other) const
{
if (abs(x - other.x) < kEps) {
return y - other.y < kEps;
}
return x - other.x < kEps;
}
};
inline bool CounterClockwise(const Point &a, const Point &b, const Point &c)
{
auto delta = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
return delta > 0;
}
Point Smallest(const vector<Point> &p)
{
Point smallest { kInf, kInf };
for (const auto &point : p) {
smallest = min(smallest, point);
}
return smallest;
}
vector<Point> ConvexHull(vector<Point> &p)
{
auto start = Smallest(p);
auto cmp = [start] (const Point &a, const Point &b) -> bool {
if (start == a) {
return true;
} else if (start == b) {
return false;
}
return CounterClockwise(start, a, b);
};
sort(p.begin(), p.end(), cmp);
vector<Point> hull;
hull.push_back(p[0]);
hull.push_back(p[1]);
for (size_t i = 2; i < p.size(); ++i) {
while (hull.size() > 1) {
const auto &a = hull[hull.size() - 2];
const auto &b = hull[hull.size() - 1];
if (CounterClockwise(a, b, p[i])) {
break;
}
hull.pop_back();
}
hull.push_back(p[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.x >> p.y;
}
auto hull = ConvexHull(points);
fout << hull.size() << "\n";
for (const auto &p : hull) {
fout << setprecision(13) << p.x << " " << p.y << "\n";
}
return 0;
}