Pagini recente » Cod sursa (job #780415) | Cod sursa (job #100394) | Cod sursa (job #3312010) | Cod sursa (job #1482307) | Cod sursa (job #3350282)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
#define double double long
using namespace std;
double d(pair<double, double> a, pair<double, double> b) {
return a.fi * b.se - a.se * b.fi;
}
double orient(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
return d(a, b) + d(b, c) + d(c, a);
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
int mn = 0;
vector<pair<double, double>> a(n);
for(int i = 0; i < n; i ++) {
cin >> a[i].fi >> a[i].se;
if(a[mn] > a[i]) {
mn = i;
}
}
swap(a[mn], a[0]);
sort(a.begin() + 1, a.end(), [&](pair<double, double> i, pair<double, double> j) {
return orient(a[0], i, j) < 0;
});
vector<pair<double, double>> stk;
stk.pb(a[0]);
stk.pb(a[1]);
for(int i = 2; i < n; i ++) {
while(stk.size() > 1 && orient(stk[stk.size() - 2], stk[stk.size() - 1], a[i]) > 0) {
stk.pop_back();
}
stk.push_back(a[i]);
}
cout << stk.size() << '\n';
reverse(stk.begin(), stk.end());
for(auto &[i, j] : stk) {
cout << fixed << setprecision(6) << i << ' ' << j << '\n';
}
}