对于初学计算几何的OIer来说,Graham算法是个不错的凸包算法。Graham算法相比极角排序法来说,更为直观也更容易理解。
数据定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class Point { public: double x, y;
Point(double x = 0, double y = 0):x(x), y(y) {}
Point(Point a, Point b) { x = b.x - a.x; y = b.y - a.y; }
double dist(const Point& p) const { return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); }
double operator * (const Point& p) const { return x * p.y - p.x * y; }
bool operator < (const Point& p) const { return (x == p.x) ? (y < p.y) : (x < p.x); }
friend istream& operator >> (istream& in, Point& p) { in >> p.x >> p.y;
return in; } };
const int MAXN = 10000 + 5;
Point p[MAXN]; int st[MAXN], top = -1; int n;
|
主程序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| void input() { cin >> n; for(int i = 0; i < n; i++) { cin >> p[i]; } }
int main() { input(); sort(p, p + n); double ans = 0;
st[++top] = 0; st[++top] = 1;
for(int i = 2; i < n; i++) { Point u(p[st[top - 1]], p[st[top]]); Point v(p[st[top]], p[i]);
while(u * v < 0) { if(top == 0) { break; } top--; u = Point(p[st[top - 1]], p[st[top]]); v = Point(p[st[top]], p[i]); } st[++top] = i; }
for(int i = 0; i <= top - 1; i++) { ans += p[st[i]].dist(p[st[i + 1]]); } top = -1; st[++top] = 0; st[++top] = 1;
for(int i = 2; i < n; i++) { Point u(p[st[top - 1]], p[st[top]]); Point v(p[st[top]], p[i]);
while(u * v > 0) { if(top == 0) { break; } top--; u = Point(p[st[top - 1]], p[st[top]]); v = Point(p[st[top]], p[i]); } st[++top] = i; }
for(int i = 0; i <= top - 1; i++) { ans += p[st[i]].dist(p[st[i + 1]]); } top = -1;
cout << setprecision(2) << fixed << ans << endl;
return 0; }
|