Pagini recente » Cod sursa (job #1402883) | Cod sursa (job #132047) | Cod sursa (job #387880) | Cod sursa (job #1979207) | Cod sursa (job #2914162)
#include <algorithm>
#include <iterator>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ld, ld> pld;
typedef complex<ld> C;
int main(void) {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int N;
cin >> N;
vector<C> P(N);
for(int i = 0; i < N; i++) {
ld x,y;
cin >> x >> y;
P[i] = {x,y};
}
sort(P.begin(), P.end(), [](const C &A, const C &B) {
return A.real() < B.real() || (A.real() == B.real() && A.imag() < B.imag());
});
auto is_counter_clockwise = [](const C &X, const C &Y, const C &Z)->bool {
return (conj(Y-X) * (Z-Y)).imag() > 0;
};
{
auto mid = stable_partition(P.begin()+1, P.begin()+N-1, [&](const C &X) {
return is_counter_clockwise(P.front(), X, P.back());
});
reverse(mid, P.end());
}
P.push_back(P.front()); N++;
int cnt = 0;
vector<C> st(N+1);
cnt = 0;
st[cnt++] = P.front();
for(int i = 1; i < N; i++) {
auto Z = P[i];
while(cnt >= 2) {
auto X = st[cnt-2];
auto Y = st[cnt-1];
if (!is_counter_clockwise(X, Y, Z)) {
cnt--;
} else break;
}
st[cnt++] = Z;
}
cout << cnt - 1 << "\n";
for(int i = 0; i < cnt-1; i++) {
auto c = st[i];
cout << fixed << setprecision(6) << c.real() << " " << c.imag() << "\n";
}
return 0;
}