Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Borderou de evaluare (job #1042305) | Monitorul de evaluare | Cod sursa (job #3333191)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int MAXN = 120005;
const double EPS = 1e-12;
struct Punct {
double x, y;
};
Punct p[MAXN]; // Vectorul cu toate punctele
Punct hull[MAXN]; // Vectorul cu punctele de pe înfășurătoare
int n; // Numărul total de puncte
int k; // Numărul de puncte de pe înfășurătoare
Punct origine;
// Produsul vectorial
double cross(Punct A, Punct B, Punct C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
// Distanța la pătrat
double dist2(Punct A, Punct B) {
double dx = B.x - A.x;
double dy = B.y - A.y;
return dx * dx + dy * dy;
}
// Comparator pentru sortare
bool cmp(Punct A, Punct B) {
double c = cross(origine, A, B);
if (fabs(c) < EPS)
return dist2(origine, A) < dist2(origine, B);
return c > 0;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fout << fixed << setprecision(6);
// Citim punctele
fin >> n;
for (int i = 0; i < n; i++)
fin >> p[i].x >> p[i].y;
// Găsim punctul cel mai de jos
int start = 0;
for (int i = 1; i < n; i++) {
if (p[i].y < p[start].y - EPS ||
(fabs(p[i].y - p[start].y) < EPS && p[i].x < p[start].x))
start = i;
}
swap(p[0], p[start]);
origine = p[0];
// Sortăm punctele după unghi
sort(p + 1, p + n, cmp);
// Construim înfășurătoarea folosind vectorul hull
hull[0] = p[0];
hull[1] = p[1];
k = 2;
for (int i = 2; i < n; i++) {
while (k > 1 && cross(hull[k-2], hull[k-1], p[i]) < EPS) {
k = k - 1;
}
hull[k] = p[i];
k = k + 1;
}
// Afișăm înfășurătoarea
fout << k << "\n";
for (int i = 0; i < k; i++) {
fout << hull[i].x << " " << hull[i].y << "\n";
}
return 0;
}