Created
November 9, 2025 03:19
-
-
Save Mjkim-Programming/82aeff23086c94adbdc68c3526a484ee to your computer and use it in GitHub Desktop.
Graham Scan Algorithm Implementation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| // [Copy Start] | |
| struct Point { | |
| long long x, y; | |
| }; | |
| enum Orientation { CW = -1, COLLINEAR = 0, CCW = 1 }; | |
| long long ccw(const Point& a, const Point& b, const Point& c) { | |
| return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); | |
| } | |
| Orientation orientation(const Point& a, const Point& b, const Point& c) { | |
| long long v = ccw(a, b, c); | |
| if (v > 0) return CCW; | |
| if (v < 0) return CW; | |
| return COLLINEAR; | |
| } | |
| vector<Point> convex_hull(vector<Point> pts) { | |
| sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) { | |
| if (a.x == b.x) return a.y < b.y; | |
| return a.x < b.x; | |
| }); | |
| vector<Point> hull; | |
| for (auto& p : pts) { | |
| while (hull.size() >= 2 && | |
| orientation(hull[hull.size() - 2], hull.back(), p) != CCW) | |
| hull.pop_back(); | |
| hull.push_back(p); | |
| } | |
| int t = hull.size() + 1; | |
| for (int i = pts.size() - 2; i >= 0; i--) { | |
| Point p = pts[i]; | |
| while (hull.size() >= t && | |
| orientation(hull[hull.size() - 2], hull.back(), p) != CCW) | |
| hull.pop_back(); | |
| hull.push_back(p); | |
| } | |
| hull.pop_back(); | |
| return hull; | |
| } | |
| // [Copy End] | |
| int main() { | |
| int N; | |
| cin >> N; | |
| vector<Point> p(N); | |
| for (int i = 0; i < N; i++) cin >> p[i].x >> p[i].y; | |
| vector<Point> hull = convex_hull(p); | |
| cout << hull.size() << "\n"; | |
| for (int i = 0; i < hull.size(); i++) { | |
| cout << hull[i].x << " " << hull[i].y << "\n"; | |
| } | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment