Pagini recente » Cod sursa (job #1734627) | Cod sursa (job #1117261) | Cod sursa (job #1896354) | Cod sursa (job #2384700) | Cod sursa (job #3245861)
#include <bits/stdc++.h>
using namespace std;
// Structura pentru a reprezenta un punct
struct Point {
double x, y;
// Comparator pentru sortarea punctelor dupa coordonata x si, in caz de egalitate, dupa coordonata y
bool operator <(const Point& p) const {
return x < p.x || (x == p.x && y < p.y);
}
};
// Functie care calculeaza produsul vectorial intre vectorii OA si OB
// Returneaza o valoare pozitiva daca fac viraj la stanga, negativa daca fac viraj la dreapta si 0 daca sunt coliniare
double cross(const Point& O, const Point& A, const Point& B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
// Functie pentru a calcula infasuratoarea convexa folosind algoritmul lui Andrew
vector<Point> convexHull(vector<Point>& points) {
int n = points.size();
if (n < 3) return {}; // Daca avem mai putin de 3 puncte, nu putem forma un poligon
// Sortam punctele dupa coordonata x (si dupa y daca x este egal)
sort(points.begin(), points.end());
// Vector pentru infasuratoarea convexa
vector<Point> hull;
// Construim partea de jos (lower hull)
for (int i = 0; i < n; ++i) {
while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0)
hull.pop_back(); // Eliminam punctul daca nu face viraj la stanga
hull.push_back(points[i]);
}
// Construim partea de sus (upper hull)
int lower_size = hull.size();
for (int i = n-1; i >= 0; --i) {
while (hull.size() > lower_size && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0)
hull.pop_back();
hull.push_back(points[i]);
}
// Eliminam ultimul punct deoarece este egal cu primul (inchidem poligonul)
hull.pop_back();
return hull;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
cin >> N;
vector<Point> points(N);
for (int i = 0; i < N; ++i) {
fin >> points[i].x >> points[i].y;
}
// Calculam infasuratoarea convexa
vector<Point> hull = convexHull(points);
// Scriem rezultatul
fout << hull.size() << '\n';
fout << fixed << setprecision(6);
for (const Point& p : hull) {
fout << p.x << " " << p.y << '\n';
}
return 0;
}