Pagini recente » Cod sursa (job #1727866) | Cod sursa (job #2059588) | Cod sursa (job #2511112) | Cod sursa (job #713898) | Cod sursa (job #3270971)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point {
long double x, y;
};
vector<Point> points;
int n;
void read() {
fin >> n;
long double x, y;
for (int i = 1; i <= n; ++i) {
fin >> x >> y;
points.emplace_back(x, y);
}
}
void selectLowestPoint() {
int lowestPointIndex = 0;
for (int i = 1; i < n; ++i) {
if (points[i].x < points[lowestPointIndex].x || (points[i].x == points[lowestPointIndex].x && points[i].y < points[lowestPointIndex].y)) {
lowestPointIndex = i;
}
}
swap(points[0], points[lowestPointIndex]);
}
long double crossProduct(const Point& a, const Point& b, const Point& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
void sortPoints() {
selectLowestPoint();
sort(points.begin() + 1, points.end(), [](const Point& x, const Point& y) {
return crossProduct(points[0], x, y) < 0;
});
}
void convexHull() {
vector<Point> stk;
stk.push_back(points[0]);
stk.push_back(points[1]);
for (int i = 2; i < n; ++i) {
while (stk.size() > 2 && crossProduct(stk[stk.size() - 2], stk[stk.size() - 1], points[i]) > 0) {
stk.pop_back();
}
stk.push_back(points[i]);
}
reverse(stk.begin(), stk.end());
fout << fixed;
fout << stk.size() << '\n';
for (const auto& p: stk) {
fout << setprecision(12) << p.x << ' ' << p.y << '\n';
}
}
int main() {
read();
sortPoints();
convexHull();
return 0;
}