Pagini recente » Borderou de evaluare (job #1607496) | Borderou de evaluare (job #2693939) | Borderou de evaluare (job #292250) | Borderou de evaluare (job #1524428) | Cod sursa (job #2501590)
#include <bits/stdc++.h>
#define x first
#define y second
#define Point std::pair <double, double>
const int MAX_N = 120005;
int n;
int st[MAX_N];
std::pair <double, double> arr[MAX_N];
double cross_product(std::pair <double, double> a, std::pair <double, double> b,
std::pair <double, double> c) {
return ((a.x * b.y) + (b.x * c.y) + (c.x * a.y) - (a.y * b.x) - (b.y * c.x) - (c.y * a.x));
}
int compare_points(const std::pair <double, double> &a, const std::pair <double, double> &b) {
return (cross_product(arr[0], a, b) < 0);
}
int main() {
int pos, k;
double x_c, y_c;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
std::cin >> n;
for (int i = 0; i < n; ++i) {
std::cin >> x_c >> y_c;
arr[i] = std::make_pair(x_c, y_c);
}
pos = 0;
for (int i = 1; i < n; ++i) {
if (arr[i] < arr[pos]) {
pos = i;
}
}
std::swap(arr[pos], arr[0]);
std::sort(arr + 1, arr + n, compare_points);
st[1] = 0;
st[2] = 1;
k = 2;
for (int i = 2; i < n; ++i) {
while (k >= 2 && cross_product(arr[st[k - 1]], arr[st[k]], arr[i]) > 0) {
--k;
}
st[++k] = i;
}
std::cout << k << "\n";
for (int i = k; i >= 1; --i) {
std::cout << std::fixed << std::setprecision(9) << arr[st[i]].x << " " << arr[st[i]].y << "\n";
}
return 0;
}