Pagini recente » Cod sursa (job #1372343) | Cod sursa (job #2486584) | Cod sursa (job #2757557) | Cod sursa (job #607053) | Cod sursa (job #2914157)
#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;
};
vector<C> hull;
int cnt;
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;
}
copy(st.begin(), st.begin() + cnt-1, std::back_inserter(hull));
}
{
cnt = 0;
st[cnt++] = P.back();
for(int i = N-2; i >= 0; 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;
}
copy(st.begin(), st.begin() + cnt-1, std::back_inserter(hull));
}
cout << hull.size() << "\n";
for(auto c: hull) {
cout << fixed << setprecision(6) << c.real() << " " << c.imag() << "\n";
}
return 0;
}