Pagini recente » Cod sursa (job #3350175) | Cod sursa (job #3318149) | Cod sursa (job #295529) | Cod sursa (job #1928441) | Cod sursa (job #3333185)
#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];
Punct stiva[MAXN];
int n, top;
// Produsul vectorial (B-A) x (C-A)
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);
}
// Distanta la patrat
double dist2(Punct A, Punct B) {
double dx = B.x - A.x;
double dy = B.y - A.y;
return dx * dx + dy * dy;
}
// Punctul origine pentru sortare
Punct origine;
// Comparator pentru sortare dupa unghi polar
bool cmp(Punct A, Punct B) {
double c = cross(origine, A, B);
if (fabs(c) < EPS) // coliniare - cel mai apropiat primul
return dist2(origine, A) < dist2(origine, B);
return c > 0; // sens trigonometric
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fout << fixed << setprecision(6);
fin >> n;
for (int i = 0; i < n; i++)
fin >> p[i].x >> p[i].y;
// 1) Gasim punctul cel mai de JOS (la egalitate, cel mai din STANGA)
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];
// 2) Sortam celelalte puncte dupa unghi polar
sort(p + 1, p + n, cmp);
// 3) Graham Scan
stiva[0] = p[0];
stiva[1] = p[1];
top = 2;
for (int i = 2; i < n; i++) {
// Cat timp avem cotitură la dreapta sau coliniare, eliminam
while (top > 1 && cross(stiva[top-2], stiva[top-1], p[i]) < EPS)
top--;
stiva[top++] = p[i];
}
// Afisare
fout << top << "\n";
for (int i = 0; i < top; i++)
fout << stiva[i].x << " " << stiva[i].y << "\n";
return 0;
}