Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define sz(x) static_cast<int>((x).size())
- #define pd pair<double,double>
- #define x first
- #define y second
- using namespace std;
- ifstream fin("infasuratoare.in");
- ofstream fout("infasuratoare.out");
- const double EPS = 1e-12;
- bool check(pd O, pd A, pd B) {
- return ((A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y)) < EPS;
- }
- int main() {
- int N;
- fin >> N;
- vector<pd> a(N);
- for(pd &x : a)
- fin >> x.x >> x.y;
- sort(a.begin(), a.end());
- vector<int> S;
- S.emplace_back(0), S.emplace_back(1);
- vector<bool> viz(N);
- viz[1] = true;
- for(int i = 0, add = 1; i >= 0; i += (add = (i == N - 1 ? -add : add))) {
- if(viz[i])
- continue;
- while(sz(S) > 1 && check(a[S[sz(S) - 2]], a[S.back()], a[i])) {
- viz[S.back()] = false;
- S.pop_back();
- }
- S.emplace_back(i);
- viz[i] = true;
- }
- fout << sz(S) - 1 << '\n' << fixed << setprecision(12);
- for(int i = 0; i < sz(S) - 1; ++i)
- fout << a[S[i]].x << ' ' << a[S[i]].y << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement