Pagini recente » Cod sursa (job #734273) | Cod sursa (job #3300920) | Cod sursa (job #739637) | Cod sursa (job #1840904) | Cod sursa (job #3300922)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define EPSILON 1e-12
#define SIZE 120001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
double X, Y;
} p[SIZE], hull[SIZE];
double cross(Point A, Point B, Point C);
int comp(const void *a, const void *b);
void build(int n, int &k) {
qsort(p, n, sizeof(Point), comp);
for (int i = 0; i < n; ++i) {
while (k >= 2 && cross(hull[k - 2], hull[k - 1], p[i]) <= 0)
--k;
hull[k++] = p[i];
}
for (int i = n - 2, t = k + 1; i >= 0; --i) {
while (k >= t && cross(hull[k - 2], hull[k - 1], p[i]) <= 0)
--k;
hull[k++] = p[i];
}
--k;
}
int main() {
int n, k = 0;
fin >> n;
for (int i = 0; i < n; ++i)
fin >> p[i].X >> p[i].Y;
build(n, k);
fout << k << '\n';
for (int i = 0; i < k; ++i)
fout << fixed << setprecision(12) << hull[i].X << ' ' << hull[i].Y << '\n';
}
double cross(Point A, Point B, Point C) {
return (B.X - A.X) * (C.Y - A.Y) - (B.Y - A.Y) * (C.X - A.X);
}
int comp(const void *a, const void *b) {
Point *nouA = ((Point *) a);
Point *nouB = ((Point *) b);
if (nouA -> X < nouB -> X)
return -1;
if (nouA -> X > nouB -> X)
return 1;
if (nouA -> Y < nouB -> Y)
return -1;
if (nouA -> Y > nouB -> Y)
return 1;
return 0;
}