Pagini recente » Cod sursa (job #61587) | Cod sursa (job #671909) | Cod sursa (job #2228439) | Cod sursa (job #2814547) | Cod sursa (job #3138792)
#include <bits/stdc++.h>
#include <iomanip>
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);
}
double x;
double y;
int main() {
std::ifstream cin("infasuratoare.in");
std::ofstream cout("infasuratoare.out");
int n; cin >> n;
std::vector<std::pair<double, double>> points(n);
for (int i = 0; i < n; ++i) {
double x; cin >> x;
double y; cin >> y;
points[i] = std::make_pair(x, y);
}
int k = 0;
for (int i = 1; i < n; ++i) {
if (points[i] < points[k]) {
k = i;
}
}
std::swap(points[k], points[0]);
x = points[0].first;
y = points[1].second;
sort(
points.begin() + 1,
points.end(),
[](auto a, auto b) {
return product(std::make_pair(x, y), a, b) < 0;
}
);
std::vector<int> st(n);
int head = 1;
st[0] = 0;
st[1] = 1;
for (int i = 2; i < n; ++i) {
while (
head >= 1 &&
product(points[st[head - 1]], points[st[head]], points[i]) > 0
) {
--head;
}
st[++head] = i;
}
cout << head + 1 << "\n";
for (int i = head; i >= 0; --i) {
cout << std::setprecision(9) << points[st[i]].first << " " << points[st[i]].second << '\n';
}
return 0;
}