Pagini recente » 795353277152115x | Cod sursa (job #1903355) | Cod sursa (job #1627538) | Cod sursa (job #2975260) | Cod sursa (job #3197610)
#include <bits/stdc++.h>
using namespace std;
using punct = pair<long double, long double>;
double det(const punct& a, const punct& b, const punct& c) {
return a.first * b.second
+ b.first * c.second
+ a.second * c.first
- b.second * c.first
- a.second * b.first
- c.second * a.first;
}
int main() {
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
in >> n;
vector<punct> points(n);
for (auto& point : points)
in >> point.first >> point.second;
auto left_point = ranges::min_element(points, {}, &punct::first);
iter_swap(points.begin(), left_point);
sort(next(points.begin()), points.end(),
[&points](const punct& a, const punct& b) {
return det(points.front(), a, b) >= 0;
} );
vector<punct> st(n);
int index = 0;
st[index] = points.front();
for (int i = 1; i < n; i++) {
while (index > 0 && det(st[index-1], st[index], points[i]) >= 0)
index--;
st[index++] = points[i];
}
out << index + 1 << '\n';
out << setprecision(6);
for (auto point : st | views::take(index))
out << point.first << ' ' << point.second << '\n';
out << points.front().first << ' ' << points.front().second << endl;
}