Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define double long double
- #define int long long
- using namespace std;
- const double EPS = 1e-8;
- template<typename T> struct Vector {
- T x, y;
- Vector(T x = 0, T y = 0): x(x), y(y) {};
- Vector operator+ (const Vector &other) {
- return Vector(x + other.x, y + other.y);
- }
- Vector operator- (const Vector &other) {
- return Vector(x - other.x, y - other.y);
- }
- T operator* (const Vector &other) {
- return x * other.x + y * other.y;
- }
- Vector operator* (const double &other) {
- return Vector(x * other, y * other);
- }
- T operator% (const Vector &other) {
- return x * other.y - y * other.x;
- }
- double abs() {
- return sqrt(x * x + y * y);
- }
- istream & operator>> (istream & in) {
- T x_, y_;
- in >> x_ >> y_;
- x = x_, y = y_;
- return in;
- }
- };
- template<typename T> struct Point {
- T x, y;
- Point(T x = 0, T y = 0): x(x), y(y) {};
- Point operator+ (const Vector<T> &other) {
- return Point(x + other.x, y + other.y);
- }
- Vector<T> operator- (const Point &B) {
- return Vector<T>(x - B.x, y - B.y);
- }
- bool operator< (const Point &B) {
- return (B.x == x ? y < B.y : x < B.x);
- }
- };
- template<typename T> bool cw(Vector<T> A, Vector<T> B) {
- return (A % B < -EPS);
- }
- template<typename T> bool ccw(Vector<T> A, Vector<T> B) {
- return (A % B > EPS);
- }
- template<typename T> double dist(Point<T> A, Point<T> Q, Point<T> P) {
- if ((A - Q) * (P - Q) < 0) return min((A - P).abs(), (A - Q).abs());
- return abs((A - P) % (Q - P)) / (Q - P).abs();
- }
- template<typename T> istream & operator>> (istream & in, Point<T> &a) {
- T x_, y_;
- in >> x_ >> y_;
- a.x = x_, a.y = y_;
- return in;
- }
- signed main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- freopen("hull.in", "r", stdin);
- freopen("hull.out", "w", stdout);
- vector<Point<int>> lower, upper, all_points;
- int n;
- cin >> n;
- all_points.resize(n);
- for (int i = 0; i < n; i++) cin >> all_points[i];
- sort(all_points.begin(), all_points.end());
- Vector<int> pivot = all_points.back() - all_points.front();
- for (int i = 0; i < n; i++) {
- if (i == 0 || i == n - 1) upper.push_back(all_points[i]), lower.push_back(all_points[i]);
- else if (cw(all_points[i] - all_points.front(), pivot)) upper.push_back(all_points[i]);
- else lower.push_back(all_points[i]);
- }
- vector<Point<int>> uh, lh;
- for (int i = 0; i < upper.size(); i++) {
- while(uh.size() > 1 && !cw(uh.back() - uh[uh.size() - 2], upper[i] - uh.back())) uh.pop_back();
- uh.push_back(upper[i]);
- }
- for (int i = 0; i < lower.size(); i++) {
- while(lh.size() > 1 && !ccw(lh.back() - lh[lh.size() - 2], lower[i] - lh.back())) lh.pop_back();
- lh.push_back(lower[i]);
- }
- cout << lh.size() + uh.size() - 2 << "\n";
- for (auto i : lh) cout << i.x << " " << i.y << "\n";
- for (int i = uh.size() - 2; i >= 1; i--) cout << uh[i].x << " " << uh[i].y << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement