Pagini recente » Cod sursa (job #2325958) | Cod sursa (job #3170673) | Cod sursa (job #622221) | Cod sursa (job #2499039) | Cod sursa (job #3159119)
#include <bits/stdc++.h>
#define MAXN 120000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double EPS = 0.00001;
struct point {
double x, y;
};
double det(point a, point b, point c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int main() {
int n;
point arr[MAXN];
fin >> n;
for (int i = 0; i < n; i++)
fin >> arr[i].x >> arr[i].y;
sort(arr, arr + n, [](point a, point b) {
if (a.x == b.x)
return a.y > a.y;
return a.x < b.x;
});
int k = 0;
int st[MAXN];
bool c[MAXN];
memset(c, false, sizeof(c));
for (int i = 0; i < n; i++) {
if (c[i]) continue;
while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0) {
c[st[--k]] = true;
}
st[k++] = i;
}
for (int i = n - 1; i >= 0; i--) {
if (c[i]) continue;
while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0) {
c[st[--k]] = true;
}
st[k++] = i;
}
fout << k << '\n';
for (int i = 0; i < k; i++)
fout << arr[st[i]].x << ' ' << arr[st[i]].y << '\n';
return 0;
}