Pagini recente » Cod sursa (job #1168386) | Cod sursa (job #2482895) | Cod sursa (job #1992280) | Cod sursa (job #136344) | Cod sursa (job #1947100)
#include <cmath>
#include <algorithm>
#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 &p) const
{
return (x == p.x) && (y == p.y);
}
};
inline bool Smaller(double a, double b)
{
return (a - b) < kEps;
}
inline bool Equal(double a, double b)
{
return abs(a - b) <= kEps;
}
bool CounterClock(const Point &a, const Point &b, const Point &c)
{
double delta = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
return delta > 0;
}
vector<Point> ConvexHull(vector<Point> &vec)
{
Point left = {kInf, kInf};
for (const auto &p : vec) {
if (Smaller(p.x, left.x) ||
(Equal(p.x, left.x) && Smaller(p.y, left.y))) {
left = p;
}
}
auto cmp = [left](const Point &a, const Point &b) -> bool {
if (a == left) {
return true;
}
if (b == left) {
return false;
}
return CounterClock(left, a, b);
};
sort(vec.begin(), vec.end(), cmp);
vector<Point> hull(2);
hull[0] = vec[0];
hull[1] = vec[1];
Point second = hull[0];
for (unsigned i = 2; i < vec.size(); ++i) {
while (hull.size() > 2 && !CounterClock(second, hull.back(), vec[i])) {
hull.pop_back();
second = hull[hull.size() - 2];
}
second = hull.back();
hull.push_back(vec[i]);
}
return hull;
}
int main()
{
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
vector<Point> points(n);
for (int i = 0; i < n; ++i) {
fin >> points[i].x >> points[i].y;
}
auto hull = ConvexHull(points);
fout << hull.size() << "\n";
for (const auto &point : hull) {
fout << fixed << setprecision(12) << point.x << " " << point.y << "\n";
}
return 0;
}