hdu 3263 Ancient vending machine


		题目：给定一个多边形A，问能否穿过多边形的洞B。
分析：计算几何、凸包、旋转卡壳、点与多边形关系。问题实际是在求多边形A的最小宽度和多边形B能容纳的最常线段长度。
                                                                                                     
1.对于多边形A，构造凸包利用，旋转卡壳求出对踵点对，然后求出最小的高。
   
                                 
2. 对于多边形B，所求的最长线段，一定经过多边形上的至少两个点，枚举所有点对，计算被截取的最长部分即可。
[cpp]  
#include <algorithm>  
#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
#include <cmath>  
  
using namespace std;  
  
typedef struct pnode  
{  
    double x,y,d;  
    pnode( double a, double b ) {x = a;y = b;}  
    pnode(){};  
}point;  
point H[ 21 ];  
point C[ 21 ];  
point P0,Pn;  
  
typedef struct lnode  
{  
    double x,y,dx,dy,d;  
    int    id,hit,sign;  
    lnode( point a, point b ) {x = a.x;y = a.y;dx = b.x-a.x;dy = b.y-a.y;}  
    lnode(){};  
}line;  
  
//两点间距离   
double dist( point a, point b )  
{  
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));  
}  
  
//点到直线距离   
double dist( point a, line l )  
{  
    return fabs(l.dx*(a.y-l.y)-l.dy*(a.x-l.x))/sqrt(l.dx*l.dx+l.dy*l.dy);  
}  
  
//叉乘 ab*ac   
double crossproduct( point a, point b, point c )  
{  
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(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 )  
{  
    double cp = crossproduct( P0, a, b );  
    if ( cp == 0 ) return a.d < b.d;  
    else return cp > 0;  
}  
  
//凸包扫描算法   
double Graham( int N )  
{  
    sort( C+0, C+N, cmp1 );  
    P0 = C[0];  
    for ( int i = 1 ; i < N ; ++ i )  
        C[i].d = dist( P0, C[i] );  
    sort( C+1, C+N, cmp2 );  
          
    //计算凸包   
    int top = 2;  
    for ( int i = 3 ; i < N ; ++ i ) {  
        while ( top > 0 && crossproduct( C[top-1], C[top], C[i] ) <= 0 ) -- top;  
        C[++ top] = C[i];  
    }  
    C[++ top] = C[0];  
      
    //旋转卡壳，求对踵点对   
    int    L = 0,R = 1;  
    double D = 500.000;  
    do{  
        while ( crossproduct( C[R], C[L], C[(L+1)%top] ) <= crossproduct( C[(R+1)%top], C[L], C[(L+1)%top] ) )  
            R = (R+1)%top;  
          
        D = min( D, dist( C[R], line( C[L], C[(L+1)%top] ) ) );  
        L = (L+1)%top;  
    }while ( L );  
      
    return D;  
}  
  
//直线与线段相交判断   
bool l_cross_s( line b, line a )  
{  
    double t1 = b.dx*(a.y-b.y)-b.dy*(a.x-b.x);  
    double t2 = b.dx*(a.y+a.dy-b.y)-b.dy*(a.x+a.dx-b.x);  
    return t1*t2 < 0;  
}  
  
//线段相交     
bool s_cross_s( line a, line b )    
{    
    double t1 = 0.0+a.dx*(b.y-a.y)-a.dy*(b.x-a.x);    
    double t2 = 0.0+a.dx*(b.y+b.dy-a.y)-a.dy*(b.x+b.dx-a.x);    
    double t3 = 0.0+b.dx*(a.y-b.y)-b.dy*(a.x-b.x);    
    double t4 = 0.0+b.dx*(a.y+a.dy-b.y)-b.dy*(a.x+a.dx-b.x);    
    return (t1*t2 < 0)&&(t3*t4 < 0);    
}  
  
//点在线段上     
bool on( point p, line l )    
{    
    if ( l.dx*(p.y-l.y)-l.dy*(p.x-l.x) == 0 )    
    if ( (p.x-l.x)*(p.x-l.x-l.dx) <= 0 )    
    if ( (p.y-l.y)*(p.y-l.y-l.dy) <= 0 )    
        return true;    
    return false;    
}    
    
//点在多边形内    
bool in( point p, point* P, int n )    
{    
    double d[4][2] = {-101,-103,-103,101,101,-103,101,103};    
    for ( int t = 0 ; t < 4 ; ++ t ) {    
        line s1 = line( p, point( d[t][0], d[t][1] ) );    
        int  count = 0;    
        for ( int i = 0 ; i < n ; ++ i ) {    
            line s2 = line( P[i], P[i+1] );    
            if ( on( p, s2 ) ) return true;    
            if ( s_cross_s( s1, s2 ) ) count ++;    
            if ( on( P[i], s1 ) && l_cross_s( s1, line( P[i+1], P[(i-1+n)%n] ) ) ) count ++;    
        }  
        if ( count%2 == 0 ) return false;     
    }    
    return true;    
}    
&

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