題目：給你一個多邊形的磚塊，要放入最小凸多邊形的地板塊中，問余下的空間占凸多邊形的面積百分比。 分析：計算幾何、凸包。求出凸包、然後用多邊形與凸包面積差，除以凸包的面積即可。 注意：點的方向的有正有負，矢量面積需要去絕對值。 [cpp] #include <algorithm> #include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> using namespace std; //點結構 typedef struct pnode { int x,y,d; }point; point P[106]; //叉乘ab*ac int crossproduct( point a, point b, point c ) { return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } //點到點距離 int dist( point a, point b ) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } //坐標排序 bool cmp1( point a, point b ) { return (a.x==b.x)?(a.y<b.y):(a.x<b.x); } //級角排序 bool cmp2( point a, point b ) { double cp = crossproduct( P[0], a, b ); if ( !cp ) return a.d < b.d; else return cp > 0; } //計算凸包 double Graham( int n ) { double S1 = 0.0; for ( int i = 1 ; i < n-1 ; ++ i ) S1 += 0.5*crossproduct( P[0], P[i], P[i+1] ); sort( P+0, P+n, cmp1 ); for ( int i = 1 ; i < n ; ++ i ) P[i].d = dist( P[0], P[i] ); sort( P+1, P+n, cmp2 ); int top = 1; for ( int i = 2 ; i < n ; ++ i ) { while ( top > 0 && crossproduct( P[top-1], P[top], P[i] ) <= 0 ) -- top; P[++ top] = P[i]; } double S2 = 0.0; for ( int i = 1 ; i < top ; ++ i ) S2 += 0.5*crossproduct( P[0], P[i], P[i+1] ); return 100.0*(fabs(S2)-fabs(S1))/fabs(S2); } int main() { int n,t = 1; while ( scanf("%d",&n) && n ) { for ( int i = 0 ; i < n ; ++ i ) scanf("%d%d",&P[i].x,&P[i].y); printf("Tile #%d\n",t ++); printf("Wasted Space = %.2lf %%\n\n",Graham( n )); } return 0; }
