UVa 10065 - Useless Tile Packers

题目：给你一个多边形的砖块，要放入最小凸多边形的地板块中，问余下的空间占凸多边形的面积百分比。
 
分析：计算几何、凸包。求出凸包、然后用多边形与凸包面积差，除以凸包的面积即可。
 
注意：点的方向的有正有负，矢量面积需要去绝对值。
 
[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;  
}

补充：软件开发 , C++ ,