# 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';
}
}
```