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;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目