Pagini recente » Cod sursa (job #1124040) | Cod sursa (job #1072698) | Cod sursa (job #2298040) | Cod sursa (job #2639739) | Cod sursa (job #1941726)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
const double kEps = 1e-12;
const double kInf = 1e10;
struct Point
{
double x, y;
bool operator==(const Point &a) const {
return (x == a.x) && (y == a.y);
}
};
Point RightLower(const Point &a, const Point &b)
{
if (a.x - b.x > kEps) {
return a;
}
if (a.x - b.x < kEps) {
return b;
}
return (a.y - b.y < kEps) ? a : b;
}
bool CounterClockwise(const Point &a, const Point &b, const Point &c)
{
double res = a.x * (b.y - c.y) + a.y * (c.x - b.x) + b.x * c.y - b.y * c.x;
return (res > kEps);
}
vector<Point> ConvexHull(vector<Point> &vec)
{
Point right = {-kInf, kInf};
for (const auto &p : vec) {
right = RightLower(right, p);
}
auto cmp = [right](const Point &a, const Point &b) -> bool {
if (a == right) {
return true;
}
if (b == right) {
return false;
}
if (a.y - right.y > kEps && right.y - b.y > kEps) {
return true;
}
if (b.y - right.y > kEps && right.y - a.y > kEps) {
return false;
}
double dx_a = abs(a.x - right.x);
double dy_a = abs(a.y - right.y);
double dx_b = abs(b.x - right.x);
double dy_b = abs(b.y - right.y);
if (a.y - right.y > kEps) {
return dx_a * dy_b - dx_b * dy_a < kEps;
}
return dx_a * dy_b - dx_b * dy_a > kEps;
};
sort(vec.begin(), vec.end(), cmp);
vec.push_back(right);
vector<Point> hull(3);
hull[0] = vec[0];
hull[1] = vec[1];
hull[2] = vec[2];
for (unsigned i = 3; i < vec.size(); ++i) {
while (!CounterClockwise(hull[hull.size() - 2], hull.back(), vec[i])) {
hull.pop_back();
}
hull.push_back(vec[i]);
}
hull.pop_back();
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 &p : hull) {
fout << setprecision(12) << p.x << " " << p.y << "\n";
}
return 0;
}