Pagini recente » Cod sursa (job #1664227) | Cod sursa (job #2367481) | Cod sursa (job #318100) | Cod sursa (job #1218984) | Cod sursa (job #3350279)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
#define double double long
using namespace std;
int d(pair<int, int> a, pair<int, int> b) {
return a.fi * b.se - a.se * b.fi;
}
int orient(pair<int, int> a, pair<int, int> b, pair<int, int> 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<int, int> i, pair<int, int> 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';
for(auto &[i, j] : stk) {
cout << fixed << setprecision(6) << i << ' ' << j << '\n';
}
}