Pagini recente » Cod sursa (job #981232) | Cod sursa (job #662735) | Cod sursa (job #1740294) | Cod sursa (job #3170199) | Cod sursa (job #2268238)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int MAXN = 13e4;
int n;
pair<double, double> p;
pair<double, double> Points[MAXN + 1], pol[MAXN + 1];
double det(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
return (a.first - c.first) * (b.second - c.second) - (a.second - c.second) * (b.first - c.first);
}
bool cmp(pair<double, double> a, pair<double, double> b) {
return det(Points[0], a, b) > det(Points[0], b, a);
}
int main() {
in >> n;
for (int i = 1; i <= n; ++ i) {
in >> p.first >> p.second;
Points[i - 1] = p;
}
sort(Points, Points + n, cmp);
pol[0] = Points[0];
pol[1] = Points[1];
int cur = 2;
for (int i = 2; i < n; ++ i) {
if (det(pol[cur - 2], pol[cur - 1], Points[i]) <= 0) -- cur;
pol[cur ++] = Points[i];
}
out << cur << '\n';
for (int i = 0; i < cur; ++ i) out << fixed << setprecision(12) << pol[i].first << ' ' << pol[i].second << '\n';
return 0;
}