Pagini recente » Cod sursa (job #166724) | Cod sursa (job #817730) | Cod sursa (job #1290820) | Cod sursa (job #1364445) | Cod sursa (job #1556178)
#include <algorithm>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
typedef pair<double, double> Point;
const int NMAX = 120005;
const double eps = 1e-12;
Point A[NMAX], B[NMAX];
struct cmp {
bool operator()(const Point& a, const Point& b) const {
double a1 = atan2(a.second - A[1].second, a.first - A[1].first);
double a2 = atan2(b.second - A[1].second, b.first - A[1].first);
if (abs(a1 - a2) < eps) {
return a.first < b.first;
} else {
return a1 < a2;
}
}
};
double crossProduct(const Point &o, const Point& a,
const Point &b) {
return (a.first - o.first) * (b.second - o.second) -
(a.second - o.second) * (b.first - o.first);
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> A[i].first >> A[i].second;
}
for (int i = 2; i <= n; ++i) {
if (A[i].first < A[1].first ||
(A[i].first == A[1].first && A[i].second < A[1].second)) {
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]) < eps) {
k--;
}
B[++k] = A[i];
}
fout << setprecision(12) << fixed;
fout << k << '\n';
for (int i = 1; i <= k; ++i) {
fout << B[i].first << ' ' << B[i].second << '\n';
}
fin.close();
fout.close();
}