UVA 10256 The Great Divide 凸包

   给n个红点，m个蓝点，问是否找到一条直线，使得直线一侧全是红点，另一侧全是蓝点。

   对两种点分别求凸包，然后就是判断两个凸包是否相离了..如果相离就是Yes否则就是No.判断相离就是枚举没一条边，看是否和另一个凸包相交就行了。另外还要考虑包含的情况，这里就需要判断一下是否存在某个点存在于另一类点的凸包内部。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
typedef double type;
using namespace std;
const double PI=acos(-1.0);
const double eps=1e-13;struct Point
{type x,y;Point(){}Point(type a,type b){x=a;y=b;}void read(){scanf("%lf%lf",&x,&y);}void print(){printf("%.6lf %.6lf",x,y);}};
typedef Point Vector;
Vector operator + (Vector A,Vector B)
{return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Point A,Point B)
{return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,type p)
{return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,type p)
{return Vector(A.x/p,A.y/p);
}
bool operator < (const Point &a,const Point &b)
{return a.x0) return Length(v3);else return fabs(Cross(v1,v2))/Length(v1);
}
Point GetLineProjection(Point P,Point A,Point B)//P在AB上的投影
{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& sol)
{double a=L.v.x, b=L.p.x-C.c.x, c=L.v.y, d=L.p.y-C.c.y;double e=a*a+c*c,f=2*(a*b+c*d), g=b*b+d*d-C.r*C.r;double delta=f*f-4*e*g;//判别式if (dcmp(delta)<0) return 0;//相离if (dcmp(delta)==0){t1=t2=-f/(2*e);sol.push_back(L.point(t1));return 1;}//相切t1=(-f-sqrt(delta))/(2*e); sol.push_back(L.point(t1));t2=(-f+sqrt(delta))/(2*e); sol.push_back(L.point(t2));return 2;
}
double angle(Vector v)//向量极角
{return atan2(v.y,v.x);
}
int getCircleCircleIntersection(Circle C1,Circle C2,vector& sol)
{double d = Length(C1.c-C2.c);if (dcmp(d)==0){if (dcmp(C1.r-C2.r)==0) return -1;return 0;}if (dcmp(C1.r+C2.r-d)<0) return 0;if (dcmp(fabs(C1.r-C2.r)-d)>0) return 0;double a=angle(C2.c-C1.c);double da= acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*C1.r*d));Point p1=C1.point(a-da),p2=C1.point(a+da);sol.push_back(p1);if (p1==p2) return 1;sol.push_back(p2);return 2;
}
int getTangents(Point p,Circle C,Vector* v)
{Vector u=C.c-p;double dist=Length(u);if (distrsum*rsum){double ang=acos((A.r+B.r)/sqrt(d2));a[cnt]=A.point(base+ang); b[cnt]=B.point(PI+base+ang); cnt++;a[cnt]=A.point(base-ang); b[cnt]=B.point(PI+base-ang); cnt++;}return cnt;
}
int isPointInpolygon(Point p,Point* poly,int n)
{int wn=0;for (int i=0; i0 && d1<=0 && d2>0) wn++;if (k<0 && d2<=0 && d1>0) wn--;}if (wn!=0) return 1;else return 0;
}
int ConvexHull(Point *p, int n,Point *ch)
{sort(p,p+n);int m=0;for (int i=0; i1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;ch[m++]=p[i];}int k=m;for (int 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--;return m;
}
Point b[660],r[660],chb[660],chr[660];
int n,m;
int main()
{
//    freopen("in.txt","r",stdin);while(~scanf("%d%d",&n,&m)){if (!n && !m) break;for (int i=0; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！