2008年11月 专题开发/技术/项目大版内专家分月排行榜第二2007年12月 专题开发/技术/项目大版内专家分月排行榜第二2006年8月 C/C++大版内专家分月排行榜第二
2008年9月 专题开发/技术/项目大版内专家分月排行榜第三2008年7月 专题开发/技术/项目大版内专家分月排行榜第三
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
本帖子已过去太久远了，不再提供回复功能。1229人阅读
计算几何（21）
题意：给定n个白点和m个黑点。问是否存在一条线可以将黑点和白点分开。
先分析：已最小的范围围住所有的点，就是求凸包。然后得到两个凸包，因为要分开所有的点，所以就是两个凸包不能相交。所以这道题的题意就可以变成求两个凸包是否相交（当然这题的凸包可能是点，也可能是线，当成退化的凸包就好）。
这题中n和m上限只有100，所以可以暴力枚举所有的凸包的边，是否相交（注意，还有可能包含，所以还是要判断下；只要找一个凸包上的一点，判断是否都是在另一个凸包所有边的一边，【逆时针时就是左边】）。
我这题是想nlogn复杂度的算法（如果可以解决，下次就可以出道n和m比较大的题了）
我的想法是两个凸包，先取一个凸包A，然后判断另一个凸包B是否有点在A当中，由于可能包含，所以还要判断下A在B中的情况。然后以A的最左边点（求凸包后，下标为0的就是）为原点O，逆时针的情况下，第一个点位C，那么任意点D，构成的角∠COD&180°；且每个点Di，与它前面的点Dj有∠CODi&∠CODj(i&j)，也就是所角以逆时针方向，单调递增。那么枚举凸包B上的点P，用二分法可以找到D(i)和D(i+1)使得∠COD(i+1)&=∠COP&=∠COD(i)。现在只要判断P点是否在DiD(i+1)的左边即可（用叉积就可以判断）。
总耗时nlogm+mlogn，当然还有处理消耗的时间，不过还是在nlogn复杂度内。
1)单点的时候，任一点都不会再单点内部，返回true
2)两点的时候。如果正好第二个凸包也是两点，那么判断是否在线上外，还要判断是否相交。其余情况则只用判断是否在两点所成的线上。
3）在用叉积判断点是否在凸包的外面的时候，还要注意同向和反向的情况（两者的叉积都是0，用点积可以判定同向还是反向）
#include &cstdio&
#include &cstdlib&
#include &cmath&
#include &cstring&
#include &iostream&
#include &algorithm&
#include &map&
#include &set&
#include &queue&
//基础点和向量运算
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
typedef Point V
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}
bool operator &(const Point& a, const Point& b)
return a.x&b.x||(a.x==b.x&&a.y&b.y);
const double eps=1e-10;
int dcmp(double x)//判断正负，或者等于0
if(fabs(x)&eps)return 0;else return x&0?-1:1;
bool operator==(const Point& a,const Point &b)
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
double Dot(Vector A, Vector B){return A.x*B.x+A.y*B.y;}//点积
double Length(Vector A){return sqrt(Dot(A,A));}//OA长
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}//OA和OB的夹角
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//叉积
double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}//三角形面积
Vector Rotate(Vector A,double rad)//rad为弧度，旋转rad度
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
Vector Normal(Vector A)//A的单位法向量，A不能为零向量
double L=Length(A);
return Vector(-A.y/L,A.x/L);
//点和直线
//P+tv表示一条直线，P为点，tv为方向向量
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)//求直线交点，确保存在交点，即Cross(v,w)非0
Vector u=P-Q;
double t=Cross(w,u)/Cross(v,w);
return P+v*t;
double DistanceToLine(Point P,Point A,Point B)//P点到直线AB的距离
Vector v1=B-A,v2=P-A;
return fabs(Cross(v1,v2)/Length(v1));
double DistanceToSegment(Point P,Point A,Point B)//点P到线段AB的距离
if(A==B)return Length(P-A);
Vector v1=B-A,v2=P-A,v3=P-B;
if(dcmp(Dot(v1,v2))&0)return Length(v2);
else if(dcmp(Dot(v1,v3))&0)return Length(v3);
else return fabs(Cross(v1,v2)/Length(v1));
Point GetLineProjection(Point P,Point A,Point B)//点在直线上的投影
Vector v=B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)//判断线段相交,不在端点相交
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)&0&&dcmp(c3)*dcmp(c4)&0;
bool OnSegment(Point p,Point a1,Point a2)//判断点是否在线段上（不包括端点）
return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))&0;
double ConvexPolygonArea(Point* p,int n)//多边形面积,，点按顺序
double area=0;
for(int i=1;i&n-1;i++)
area+=Cross(p[i]-p[0],p[i+1]-p[0]);
return area/2;
const int maxn=1e2+10;
int ConvexHull(Point *p,Point *ch,int n)//求凸包
sort(p,p+n);
int i,m=0,k;
for(i=0;i&n;i++)
while(m&1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])&=0)m--;
ch[m++]=p[i];
for(i=n-2;i&=0;i--)
while(m&k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])&=0)m--;
ch[m++]=p[i];
if(n&1)m--;
//if(ConvexHullIntersection(ch1,t1,ch2,t2)&&ConvexHullIntersection(ch2,t2,ch1,t1))printf(&YES\n&);else printf(&NO\n&);
bool ConvexHullIntersection(Point *ch1,int t1,Point *ch2,int t2)//判断凸包是否相交
double angle[maxn],x;
int i,j,k,m;
for(i=0;i&t2;i++)
k=dcmp(Cross(ch1[1]-ch1[0],ch2[i]-ch1[0]));
if(k==0&&Dot(ch1[1]-ch1[0],ch2[i]-ch1[0])&0)
if(Length(ch2[i]-ch1[0])&Length(ch1[1]-ch1[0]))
if(t2==2&&SegmentProperIntersection(ch1[0],ch1[1],ch2[0],ch2[1]))
angle[0]=0;
for(i=2;i&t1;i++)
angle[i-1]=Angle(ch1[1]-ch1[0],ch1[i]-ch1[0]);
for(i=0;i&t2;i++)
j=dcmp(Cross(ch1[1]-ch1[0],ch2[i]-ch1[0]));
if(j&0||(j==0&&Dot(ch1[1]-ch1[0],ch2[i]-ch1[0])&0))
j=dcmp(Cross(ch1[t1-1]-ch1[0],ch2[i]-ch1[0]));
if(j&0||(j==0&&Dot(ch1[t1-1]-ch1[0],ch2[i]-ch1[0])&0))
x=Angle(ch1[1]-ch1[0],ch2[i]-ch1[0]);
m=lower_bound(angle,angle+t1-1,x)-
if(m==0)j=0;
else j=m-1;
k=dcmp(Cross(ch1[j+1]-ch2[i],ch1[j+2]-ch2[i]));
Point p1[maxn],ch1[maxn],p2[maxn],ch2[maxn];
int n,m,t1,t2;
int main()
while(scanf(&%d%d&,&n,&m)!=EOF)
if(n==0&&m==0)
int i,j,k;
for(i=0;i&n;i++)
scanf(&%lf%lf&,&p1[i].x,&p1[i].y);
for(i=0;i&m;i++)
scanf(&%lf%lf&,&p2[i].x,&p2[i].y);
t1=ConvexHull(p1,ch1,n);
t2=ConvexHull(p2,ch2,m);
if(ConvexHullIntersection(ch1,t1,ch2,t2)&&ConvexHullIntersection(ch2,t2,ch1,t1))printf(&YES\n&);
else printf(&NO\n&);
0 0 2 0 2 2 0 2
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：375366次
积分：7380
积分：7380
排名：第2921名
原创：370篇
转载：46篇
评论：78条
(1)(1)(3)(1)(61)(56)(3)(30)(95)(95)(42)(5)(2)(1)(8)(12)扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
判断点是否在多边形内的5种方法
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
0?1:-1;}struct point{double x,y;bool
point_is_inside()
//叉积判断点在凸包内部!
只针对于凸多边形.圆心连接每一条边的端点得到的叉积必须同向.
以此可以延伸出面积法判定点是否在凸包内部.这两种方法都局限于在凸多边形{point p1;p1.x=pegx,p1.y=
为您推荐：
其他类似问题
扫描下载二维码1621人阅读
【计算几何】（16）
&timus &1215. Exactness of Projectile Hit & URAL 解题报告
题目描述真是无语，大概是一个导弹有一个落点，给定坐标； 然后有一个目标区域，问导弹的最小轰炸直径是多少时才能满足目标区域内至少有一个点被攻击到！
其实就是求点到凸包的最短距离的2倍！
首先，判断点是不是在凸包内部，是的话输出0.000
不是的话，判断点到每一条线段的距离即可，选出最短的距离就是半径，然后输出直径就好！ & 注意G++输出的时候只能用printf（“%.3f”） 而不能用lf输出…… &有懂的留言讨论下……
有两个地方需要注意：
1.判断点是否在凸包内部，假如在凸包内部的话，连续三个点，p1,p2,p3 &那么p-p1,p-p2,p-p3旋转顺序是相同的； 反之叉积&0 就不在内部， 碰到共线的情况下不用管它，肯定还有不共线的情况，如果该点不在内部的话，至于为什么会成立，我暂且不知道6
2.判断点到线段的距离，有两种方法这里
1）找到一点t是的pt与p1p2垂直，然后看看pp1与pp2是不是pt的同侧，在同侧的话是钝角三角形，那么垂足一定不再线段p1p2上；
如果在的话利用等面积法就好了，注意叉积的集合意义，其大小等于面积或者体积（2维或3维的情况）
2）或者直接利用勾股定理判断是不是钝角三角形，其目的是判断垂足是不是在线段上，然后就利用等面积法……
文中判断大小的时候貌似不太严格，double判断大小的情况请移步，小媛在努力的CSDN博客……
#include &iostream&
#include&cstdio&
#include&cmath&
#include&cstring&
#define N 100000
#define EPS 1e-7
struct Point
double x,y;
double cross(Point p,Point p1,Point p2)
{///向量pp1 * pp2
double x1=p1.x-p.x,y1=p1.y-p.y;
double x2=p2.x-p.x,y2=p2.y-p.y;
return x1*y2-x2*y1;
bool cover()
{///如果点在凸包内部的话，那么书序连接它与各个顶点，相邻的点旋转顺序一定是一样的，注意如果有点在共线的情况，先不用管他
///后来还出出现特殊情况的
pot[n]=pot[0];
pot[n+1]=pot[1];
pot[n+2]=pot[2];
for(int i=0;i&=n;++i)
if(cross(po,pot[i],pot[i+1])*cross(po,pot[i+1],pot[i+2])&0 )
///点在凸包内部
double dis2(Point p1,Point p2)
return sqrt( pow(p1.x-p2.x,2.0) +pow(p1.y-p2.y,2.0) );
double disptoseg(Point p,Point p1,Point p2)
{///返回点到线段的距离
if(dis2(p1,p2)==0)return dis2(p,p1);
Point t=///注意这里的构建,这里是构建一个点t是的pt与p1p2垂直
t.y+=p1.x-p2.x;
t.x+=p2.y-p1.y;
if( cross(t,p,p1)*cross(t,p,p2)&=0 )
{///如果是钝角
return min( dis2( p,p1),dis2(p,p2) );
///如果是锐角三角形，那么就用等面积法求解
return fabs( cross(p,p1,p2) )/ dis2(p1,p2) ;
double disptosegment(point p1, point p2, point p3)
{///点到线段距，p1为点，p2-p3为线段 这是另外一种构建方法
///如果点和点a或者点b重合
double a = dis(p1, p2);
double b = dis(p1, p3);
if(a & eps || b & eps) return 0;
///如果a,b重合，线段是一个点的情况
double c = dis(p2, p3);
if(c & eps)
///垂足不在线段上，即三角形是钝角三角形
if(a*a &= b*b+c*c)
if(b*b &= a*a+c*c)
///一般情况下就是利用等面积法
double l = (a+b+c)/2.0;
double s = sqrt(l*(l-a)*(l-b)*(l-c));
return 2.0*s/c;
int main()
while(cin&&po.x&&po.y&&n)
for(int i=0;i&n;++i)
cin&&pot[i].x&&pot[i].y;
if(cover())
cout&&0.000&&
pot[n]=pot[0];
double ans=1e30;
for(int i=0;i&n;++i)
tmp=disptoseg(po,pot[i],pot[i+1]);
if(tmp&ans)ans=
printf(&%.3f\n&,ans*2+EPS);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：83581次
积分：1600
积分：1600
排名：千里之外
原创：76篇
转载：10篇
(14)(50)(16)(6)