Pagini recente » Cod sursa (job #174971) | Cod sursa (job #1637269) | Cod sursa (job #204572) | Cod sursa (job #1570546) | Cod sursa (job #3288968)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair <double, double> Point;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double cross_product(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);
}
vector < Point > convexHull(vector < Point >& points) {
// Pas 1. Sortarea punctelor
Point p0 = points[0];
int poz = 0;
for (int32_t i = 1; i < points.size(); i++) {
if (points[i] < p0)
p0 = points[i], poz = i;
}
swap(points[0], points[poz]);
// p[0], a, b
sort(points.begin() + 1, points.end(), [&points](const Point &a, const Point &b) {
const double cp = cross_product(points[0], a, b);
if (cp == 0)
return (points[0].x-a.x)*(points[0].x-a.x) + (points[0].y-a.y)*(points[0].y-a.y) < (points[0].x-b.x)*(points[0].x-b.x) + (points[0].y-b.y)*(points[0].y-b.y);
return cp < 0;
});
// Pas 2. Determinarea punctelor de pe infasuratoarea convexa
vector < Point > ch;
ch.push_back(points[0]);
ch.push_back(points[1]);
for (int32_t i = 2; i < points.size(); i++) {
while (ch.size() > 1 && cross_product(ch[ch.size() - 2], ch[ch.size() - 1], points[i]) >= 0) {
ch.pop_back();
}
ch.push_back(points[i]);
}
return ch;
}
int main() {
int32_t N;
fin >> N;
vector<Point> points(N);
for (auto &p : points) {
fin >> p.x >> p.y;
}
// Varianta 2 - Convex Hull bazat pe Graham Scan (cu tratare caz cand punctul de start e coliniar) + Brute force
auto ch = convexHull(points);
reverse(ch.begin(), ch.end());
fout << ch.size() << '\n';
fout << setprecision(12) << fixed;
for (auto &p : ch) {
fout << p.x << ' ' << p.y << '\n';
}
}