`
阿尔萨斯
  • 浏览: 4110276 次
社区版块
存档分类
最新评论

HDU 3952 Fruit Ninja(直线与线段相交枚举)

 
阅读更多

HDU 3952 Fruit Ninja(直线与线段相交枚举)

http://blog.csdn.net/zxy_snow/article/details/6699215

题意:

平面上给你n个凸多边形,然后问你如果画一条直线,最多能穿过多少个凸多边形. 就算相交于一点也算.

分析:

结论:假设有一条直线穿过了最多个数的多边形,那么我们一定可以通过先平移该直线,使得该直线在保持穿过多边形个数最多的前提下,只与其中一个多边形交于1点(与其他多边形的相交情况不管). 然后再旋转,使得该直线与另一个多边形也只交于一点.

由上面结论可以得出,我们只要枚举不同多边形的两个点,然后以这两点构成的直线作为目标直线,看看它到底与多少个多边形相交即可.

判断直线与多边形是否相交,只要判断该直线是否与多边形的一条线段相交即可.(注意:这里是直线与线段相交判定了)

AC代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10;
const int maxn=10+5;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}

struct Point //点
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Cross(Vector A,Vector B)//向量叉积
{
    return A.x*B.y-A.y*B.x;
}
bool LineIntersectionSegment(Point a1,Point a2,Point b1,Point b2)//判断线段a1a2是否与直线b1b2相交
{
    double c1=Cross(b2-b1,a1-b1),c2=Cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<=0;
}
struct Polygen //多边形
{
    Point p[maxn];
    int k;
}Poly[maxn];

int get_num(Point p1,Point p2,int n)//看直线p1p2与多少多边形相交
{
    int sum=0;
    for(int i=0;i<n;++i)
    for(int j=0;j<Poly[i].k;++j)
    {
        Point s1=Poly[i].p[j];
        Point s2=Poly[i].p[(j+1)%Poly[i].k];
        if(LineIntersectionSegment(s1,s2,p1,p2))
        {
            ++sum;
            break;
        }
    }
    return sum;
}

int main()
{
    int T; scanf("%d",&T);
    for(int kase=1;kase<=T;++kase)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i)
        {
            scanf("%d",&Poly[i].k);
            for(int j=0;j<Poly[i].k;++j)
                scanf("%lf%lf",&(Poly[i].p[j].x),&(Poly[i].p[j].y) );
        }
        if(n==1)
        {
            printf("Case %d: 1\n",kase);
            continue;
        }
        int ans=0;
        for(int i=0;i<n;++i)//第i个多边形
        for(int j=0;j<Poly[i].k;++j)//i多边形的第j个点
        for(int k=i+1;k<n;++k)
        for(int l=0;l<Poly[k].k;++l)
        {
            Point p1=Poly[i].p[j],p2=Poly[k].p[l];
            ans=max(ans,get_num(p1,p2,n));
        }
        printf("Case %d: %d\n",kase,ans);
    }
    return 0;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics