題目：求凸包上的點和凸包周長。 分析：計算幾何、凸包。直接利用graham算法求解即可，按順時針方向求解，注意叉乘符號。 注意：點小於3個的情況、不過我的凸包算法對n>0都可以求解、而且是所有的點。 [cpp] #include <algorithm> #include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; typedef struct pnode { double x,y,d; }point; point P[ 10000 ]; point S[ 10000 ]; point MP; double crossproduct( point a, point b, point c )//ab到ac { return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } double dist( point a, point b ) { return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y)); } bool cmp1( point a, point b ) { if ( a.x == b.x ) return a.y < b.y; else return a.x < b.x; } bool cmp2( point a, point b ) { return crossproduct( P[0], a, b ) < 0; } bool cmp3( point a, point b ) { double cp = crossproduct( P[0], a, b ); if ( cp == 0.0 ) { if ( !crossproduct( P[0], a, MP ) )//在回邊上 return a.d > b.d; else return a.d < b.d; }else return cp < 0; } double Graham( int N ) { sort( P+0, P+N, cmp1 ); sort( P+1, P+N, cmp2 ); //處理共線 for ( int i = 1 ; i < N ; ++ i ) P[i].d = dist( P[0], P[i] ); MP = P[N-1]; sort( P+1, P+N, cmp3 ); int top = -1; if ( N > 0 ) S[++ top] = P[0]; if ( N > 1 ) S[++ top] = P[1]; if ( N > 2 ) { S[++ top] = P[2]; for ( int i = 3 ; i < N ; ++ i ) { while ( crossproduct( S[top-1], S[top], P[i] ) > 0 ) -- top; S[++ top] = P[i]; } } S[++ top] = P[0]; double L = 0.0; for ( int i = 0 ; i < top ; ++ i ) { L += dist( S[i], S[i+1] ); printf("(%.1lf,%.1lf)-",S[i].x,S[i].y); }printf("(%.1lf,%.1lf)\n",S[0].x,S[0].y); printf("Perimeter length = %.2lf\n",L); return L; } int main() { int N,T = 1; while ( scanf("%d",&N) && N ) { for ( int i = 0 ; i < N ; ++ i ) scanf("%lf%lf",&P[i].x,&P[i].y); if ( T > 1 ) printf("\n"); printf("Region #%d:\n",T ++); Graham( N ); } return 0; }
