# ZeroJudge - b596: Less is better ### 題目連結:https://zerojudge.tw/ShowProblem?problemid=b596 ###### tags: `ZeroJudge` `數學` `幾何` ```cpp= #include <iostream> #include <algorithm> using namespace std; int vertices, convexAmount; struct point { int x, y, index; bool operator<(const point &other) const { if (this->x != other.x) return this->x < other.x; return this->y < other.y; } } points[10000], convex[10005]; int CrossProduct(point o, point a, point b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); } int Distance(point a, point b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } void FindConvexHull() { for (int i = 0; i < vertices; ++i) { while (convexAmount >= 2 && CrossProduct(convex[convexAmount - 2], convex[convexAmount - 1], points[i]) <= 0) --convexAmount; convex[convexAmount] = points[i]; ++convexAmount; } for (int i = vertices - 2, j = convexAmount + 1; i >= 0; --i) { while (convexAmount >= j && CrossProduct(convex[convexAmount - 2], convex[convexAmount - 1], points[i]) <= 0) --convexAmount; convex[convexAmount] = points[i]; ++convexAmount; } --convexAmount; } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); while (cin >> vertices, vertices) { for (int i = 0; i < vertices; ++i) cin >> points[i].x >> points[i].y, points[i].index = i; sort(points, points + vertices); convexAmount = 0; FindConvexHull(); cout << convexAmount << '\n'; } } ```