Pagini recente » Cod sursa (job #1828252) | Cod sursa (job #1556211)
#include <algorithm>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
struct Point {
double x, y;
};
const int NMAX = 120005;
const double eps = 1e-12;
Point A[NMAX], B[NMAX];
double crossProduct(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);
}
struct cmp {
bool operator()(const Point& a, const Point& b) const {
double d = crossProduct(A[1], a, b);
if (abs(d) > eps) {
return d > 0;
} else if (abs(a.x - b.x) > eps) {
return a.x < b.x;
} else {
return a.y < b.y;
}
}
};
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> A[i].x >> A[i].y;
}
for (int i = 2; i <= n; ++i) {
if (A[i].x < A[1].x ||
(abs(A[i].x - A[1].x) < eps && A[i].y < A[1].y)) {
swap(A[1], A[i]);
}
}
sort(A + 2, A + n + 1, cmp());
int k = 1;
B[1] = A[1];
for (int i = 2; i <= n; ++i) {
while (k > 1 && crossProduct(B[k - 1], B[k], A[i]) < 0) {
k--;
}
B[++k] = A[i];
}
fout << setprecision(12) << fixed;
fout << k << '\n';
for (int i = 1; i <= k; ++i) {
fout << B[i].x << ' ' << B[i].y << '\n';
}
fin.close();
fout.close();
}