Pagini recente » Cod sursa (job #1215006) | Cod sursa (job #1680304) | Monitorul de evaluare | Cod sursa (job #173193) | Cod sursa (job #2268255)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int MAXN = 12e4;
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 = 0; i < n; ++ i) {
in >> p.first >> p.second;
Points[i] = p;
}
sort(Points, Points + n, cmp);
pol[0] = Points[0];
pol[1] = Points[1];
int cur = 2;
for (int i = 2; i < n; ++ i) {
while (cur > 1 && 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;
}