Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Andrew's monotone chain convex hull algorithm
- O(NlogN)
- */
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef complex<ll> pt;
- const int N=1e5+10;
- int n;
- vector<pt> t, hull;
- ll cross (pt a, pt b, pt c)
- {
- return imag(conj(b-a)*(c-a));
- }
- bool cmp (const pt &z, const pt &w)
- {
- if (real(z)==real(w)) return imag(z)<imag(w);
- return real(z)<real(w);
- }
- void convexHull ()
- {
- sort (t.begin(), t.end(), cmp);
- for (int i=0; i<2; i++)
- {
- int initSize=hull.size();
- for (auto xt: t)
- {
- while (hull.size()>=initSize+2 && cross(hull[hull.size()-2], hull[hull.size()-1], xt)<=0) hull.pop_back();
- hull.push_back(xt);
- }
- hull.pop_back();
- reverse(t.begin(), t.end());
- }
- }
- int main()
- {
- scanf ("%d", &n);
- t.resize(n);
- for (int i=0;i<n;i++)
- {
- ll a, b;
- scanf ("%lld%lld", &a, &b);
- t[i]=pt(a, b);
- }
- convexHull();
- printf ("%d\n", hull.size());
- for (auto xt: hull) printf ("%lld %lld\n", real(xt), imag(xt));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment