Pagini recente » Cod sursa (job #1169113) | Cod sursa (job #626679) | Cod sursa (job #3269950) | Cod sursa (job #89676) | Cod sursa (job #3141727)
#include <bits/stdc++.h>
using namespace std;
double product(
std::pair<double, double> p0,
std::pair<double, double> p1,
std::pair<double, double> p2
) {
return (p1.first - p0.first) * (p2.second - p0.second) - (p2.first - p0.first) * (p1.second - p0.second);
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n; cin >> n;
vector<pair<double, double>> points(n);
for (int i = 0; i < n; ++i) {
cin >> points[i].first >> points[i].second;
}
auto min_y_point = points[0];
double max_y = points[0].second;
for (int i = 1; i < n; ++i) {
max_y = max(max_y, points[i].second);
if (
points[i].second < min_y_point.second
|| (
points[i].second == min_y_point.second
&& points[i].first < min_y_point.first
)
) {
min_y_point = points[i];
}
}
vector<pair<double, double>> left_chain;
left_chain.push_back(min_y_point);
while (left_chain.back().second < max_y) {
auto last = left_chain.back();
auto point = points[0];
if (last == point) {
point = points[1];
}
for (int i = 0; i < n; ++i) {
if (points[i] == last) continue;
double prod = product(last, points[i], point);
if (prod < 0 || (prod == 0 && points[i].first < point.first)) {
point = points[i];
}
}
left_chain.push_back(point);
}
vector<pair<double, double>> right_chain;
right_chain.push_back(min_y_point);
while (right_chain.back().second < max_y) {
auto last = right_chain.back();
auto point = points[0];
if (last == point) {
point = points[1];
}
for (int i = 0; i < n; ++i) {
if (points[i] == last) continue;
double prod = product(last, points[i], point);
if (prod > 0 || (prod == 0 && points[i].first > point.first)) {
point = points[i];
}
}
right_chain.push_back(point);
}
left_chain.pop_back();
for (int i = left_chain.size() - 1; i >= 0; i--) {
right_chain.push_back(left_chain[i]);
}
right_chain.pop_back();
cout << right_chain.size() << endl;
for (auto p : right_chain) {
cout << setprecision(18) << p.first << " " << p.second << endl;
}
return 0;
}