Pagini recente » Cod sursa (job #17919) | Cod sursa (job #2764420) | Cod sursa (job #1033078) | Cod sursa (job #1728440) | Cod sursa (job #2988401)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
constexpr double EPSILON = 1e-12;
struct Point {
double x, y;
Point() : x(), y() {}
Point(double x, double y) : x(x), y(y) {}
};
static inline double distance(const Point& A, const Point& B) {
return (B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y);
}
static inline int orientation(const Point& A, const Point& B, const Point& C) {
double d = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
if (d <= -EPSILON / 2) return -1;
if (d >= EPSILON / 2) return 1;
return 0;
}
static inline vector<Point> convex_hull(vector<Point> polygon) {
Point P0 = *min_element(
polygon.begin(), polygon.end(),
[](const Point& A, const Point& B) {
return make_pair(A.y, A.x) < make_pair(B.y, B.x);
}
);
sort(
polygon.begin(), polygon.end(),
[&](const Point& A, const Point& B) {
const int o = orientation(P0, A, B);
if (o == 0) return distance(P0, A) < distance(P0, B);
return o > 0;
}
);
vector<Point> hull;
for (int i = 0; i < polygon.size(); ++i) {
while (hull.size() > 1 && orientation(hull[hull.size() - 2], hull[hull.size() - 1], polygon[i]) <= 0)
hull.pop_back();
hull.push_back(polygon[i]);
}
return hull;
}
int main() {
vector<Point> polygon;
double x, y;
int N, i;
fin >> N;
for (i = 1; i <= N; ++i) {
fin >> x >> y;
polygon.emplace_back(x, y);
}
const vector<Point> hull = convex_hull(polygon);
fout << hull.size() << '\n';
for (const Point& P : hull)
fout << P.x << ' ' << P.y << '\n';
fin.close();
fout.close();
return 0;
}