Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using Point = pair<int, int>;
- const int N = 100100;
- int n;
- pair<int, int> a[N];
- int det(int a, int b, int c, int d) { return a * d - b * c; }
- int det(const Point &p, const Point &q, const Point &o) {
- return det(p.first - o.first, p.second - o.second, q.first - o.first, q.second - o.second);
- }
- long long dist(const Point &p, const Point &q)
- {
- return 1LL * (p.first - q.first) * (p.first - q.first) + 1LL * (p.second - q.second) * (p.second - q.second);
- }
- int convexHull(Point *a, int n) {
- if(n < 3) return n;
- swap(*a, *min_element(a, a + n));
- sort(a + 1, a + n, [a](const Point &p, const Point &q) {
- auto d = det(p, q, a[0]);
- return d < 0 || d == 0 && dist(p, a[0]) < dist(q, a[0]);
- });
- int h = 1;
- for (int i = 2; i < n; ++i) {
- while (h > 0 && det(a[h - 1], a[h], a[i]) >= 0)
- --h;
- swap(a[++h], a[i]);
- }
- return h + 1;
- }
- int main() {
- scanf("%d", &n);
- for (int i = 0; i < n; ++i)
- scanf("%d%d", &a[i].first, &a[i].second);
- n = convexHull(a, n);
- printf("%d\n", n);
- for (int i = 0; i < n; ++i)
- printf("%d %d\n", a[i].first, a[i].second);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment