频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 3263 Ancient vending machine
2013-02-24 08:50:00           
收藏   我要投稿
题目:给定一个多边形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;    

}    

  

//两直线交点   

point crosspoint( line l, line m )  

{  

    point a = point( m.x, m.y );  

    point b = point( m.x+m.dx, m.y+m.dy );  

    if ( m.dx*l.dy == m.dy*l.dx ) {  

        if ( dist( point( l.x, l.y ), a ) < dist( point( l.x, l.y ), b ) )  

            return a;  

        else return b;  

    }else {  

        double a1 = -l.dy,b1 = l.dx,c1 = l.dx*l.y-l.dy*l.x;  

        double a2 = -m.dy,b2 = m.dx,c2 = m.dx*m.y-m.dy*m.x;  

        double x = (c1*b2-c2*b1)/(a1*b2-a2*b1);  

        double y = (c1*a2-c2*a1)/(b1*a2-b2*a1);  

        return point( x, y );  

    }   

}  

  

//计算空的最大长度   

double Calcul( int N )  

{  

    H[N] = H[0];  

      

    point  X[ 21 ];  

    double D = 0.0;  

    for ( int i = 0 ; i < N ; ++ i )  

    for ( int j = i+1 ; j < N ; ++ j ) {  

        line l = line( H[i], H[j] );  

              

        int S = 0;  

        for ( int k = 0 ; k < N ; ++ k ) {  

            line m = line( H[k], H[k+1] );  

            if ( l_cross_s( l, m ) )  

                X[S ++] = crosspoint( l, m );  

        }  

        X[S ++] = H[i];  

        X[S ++] = H[j];  

          

        P0 = point( -101, -103 );  

        for ( int k = 0 ; k < S ; ++ k )  

            X[k].d = dist( P0, X[k] );  

        sort( X, X+S, cmp2 );  

          

        double sum = 0.0;  

        int    fla = 0;  

        for ( int i = 1 ; i < S ; ++ i ) {  

            if ( in( point( (X[i-1].x+X[i].x)/2, (X[i-1].y+X[i].y)/2 ), H, N ) ) {  

                if ( fla ) sum += dist( X[i-1], X[i] );  

                else sum = dist( X[i-1], X[i] );  

                D = max( D, sum );  

                fla = 1;  

            }  

        }  

    }  

      

    return D;  

}  

  

int main()  

{  

    int T,N,M;  

    while ( scanf("%d",&T) != EOF )   

    while ( T -- ) {  

        scanf("%d",&N);  

        for ( int i = 0 ; i < N ; ++ i )  

            scanf("%lf%lf",&H[i].x,&H[i].y);  

        scanf("%d",&M);  

        for ( int i = 0 ; i < M ; ++ i )  

            scanf("%lf%lf",&C[i].x,&C[i].y);  

          

        //计算硬币最小宽度   

        double d = Graham( M );  

          

        //计算空的最大长度   

        double D = Calcul( N );  

          

        if ( d <= D ) printf("legal\n");  

        else printf("illegal\n");  

    }  

    return 0;  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:数位和乘积(高精组合数学)
下一篇:HAC-UM无线数传模块使用总结
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站