Pagini recente » Borderou de evaluare (job #2772031) | Cod sursa (job #465312) | Cod sursa (job #696603) | Cod sursa (job #2910722) | Cod sursa (job #2268220)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
vector<pair<double, double> > Points;
pair<double, double> p;
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.push_back(p);
}
sort(Points.begin(), Points.end(), cmp);
vector<pair<double, double> > pol;
pol.push_back(Points[0]);
pol.push_back(Points[1]);
for (int i = 2; i < Points.size(); ++ i) {
if (det(pol[pol.size() - 2], pol[pol.size() - 1], Points[i]) <= 0) pol.pop_back();
pol.push_back(Points[i]);
}
out << pol.size() << '\n';
for (auto x : pol) out << fixed << setprecision(12) << x.first << ' ' << x.second << '\n';
return 0;
}