Pagini recente » Cod sursa (job #1830381) | Cod sursa (job #1039914) | Cod sursa (job #2698503) | Cod sursa (job #1097533) | Cod sursa (job #3220265)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120001;
vector<pair<long double, long double>> points;
vector<pair<long double, long double>> hull1, hull2;
bool SORT(const pair<long double, long double>& a, const pair<long double, long double>& b) {
if (a.first != b.first)
return (a.first <= b.first);
return (a.second <= b.second);
}
long double AREA(pair<long double, long double> a, pair<long double, long double> b, pair<long double, long double> c) {
return a.first * b.second + b.first * c.second + c.first * a.second - b.second * c.first - c.second * a.first - a.second * b.first;
}
int main() {
int n;
in >> n;
for(int i = 0; i < n; i++) {
long double x, y;
in >> x >> y;
points.push_back({x, y});
}
sort(points.begin(), points.end(), SORT);
hull1.push_back(points[0]);
for (int i = 1; i < points.size(); i++) {
while (hull1.size() > 1 && AREA(hull1[hull1.size() - 1], hull1[hull1.size() - 2], points[i]) > 0) {
hull1.pop_back();
}
hull1.push_back(points[i]);
}
hull2.push_back(points[0]);
for (int i = 1; i < points.size(); i++) {
while (hull2.size() > 1 && AREA(hull2[hull2.size() - 1], hull2[hull2.size() - 2], points[i]) < 0) {
hull2.pop_back();
}
hull2.push_back(points[i]);
}
out << hull1.size() - 1 + hull2.size() - 1 << '\n';
for(int i = 0; i < hull1.size(); i++) {
out << fixed << setprecision(6) << hull1[i].first << " " << fixed << setprecision(6) << hull1[i].second;
out << '\n';
}
for(int i = hull2.size() - 2; i >= 0; i--) {
out << fixed << setprecision(6) << hull2[i].first << " " << fixed << setprecision(6) << hull2[i].second;
out << '\n';
}
return 0;
}
/*
8
2 0
0 2
1 3
0 4
3 3
2 6
4 2
4 4
*/