Pagini recente » Cod sursa (job #221722) | Cod sursa (job #2083860) | Cod sursa (job #1886391) | Cod sursa (job #3159846) | Cod sursa (job #3159134)
#include <bits/stdc++.h>
#define MAXN 1200000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double det(
pair<double, double> a,
pair<double, double> b,
pair<double, double> c
) {
return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}
pair<double, double> arr[MAXN];
int main() {
int n;
fin >> n;
for (int i = 0; i < n; i++)
fin >> arr[i].first >> arr[i].second;
sort(arr, arr + n);
int k = 0, st[MAXN];
for (int i = 0; i < n; i++) {
while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0)
k--;
st[k++] = i;
}
for (int i = n - 2; i >= 0; i--) {
while (k > 1 && det(arr[st[k - 2]], arr[st[k - 1]], arr[i]) < 0)
k--;
st[k++] = i;
}
fout << fixed << setprecision(6) << k - 1 << '\n';
for (int i = 0; i < k - 1; i++)
fout << arr[st[i]].first << ' ' << arr[st[i]].second << '\n';
return 0;
}