UVA 10256 The Great Divide(凸包应用)
题意:
有n个红点和m个蓝点,问你是否存在一条直线,使得任取任取一个红点和一个蓝点,都在直线的两边?这条直线不能穿过红点或蓝点.
分析:
刘汝佳<<训练指南>> P274例题8
先求出红点的凸包和蓝点的凸包,则分离两个点集的充要条件是分离两个凸包.
只要两个凸包没有任何一个公共点,那么就可以用直线分离点集.
什么情况下两个凸包不存在任何一个公共点呢?
1. 构成两个凸包的任意两条线段不相交(一个公共点都没有).
2. 一个凸包的任意点都在另一个凸包的外面.
当凸包退化成线段或点时,需要特殊处理的.不过程序代码中并没有特殊处理,因为代码中的模板能处理退化后的情况.不过还是要自己分析一下,到底当一个凸包退化成1个点或线段时,会出现什么情况?
AC代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10;
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){}
bool operator==(const Point &B)const
{
return dcmp(x-B.x)==0 && dcmp(y-B.y)==0;
}
bool operator<(const Point &B)const
{
return dcmp(x-B.x)<0 ||(dcmp(x-B.x)==0 && dcmp(y-B.y)<0);
}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
return Vector(A.x-B.x,A.y-B.y);
}
double Dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
bool InSegment(Point P,Point A,Point B)
{//A==B时也能正确运行
return dcmp(Cross(A-P,B-P))==0 && dcmp(Dot(A-P,B-P))<=0;
}
bool SegmentIntersection(Point a1,Point a2,Point b1,Point b2)
{//a1==a2或b1==b2时,也能正确运行
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);
double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
if(dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0) return true;
if(dcmp(c1)==0 && InSegment(b1,a1,a2) ) return true;
if(dcmp(c2)==0 && InSegment(b2,a1,a2) ) return true;
if(dcmp(c3)==0 && InSegment(a1,b1,b2) ) return true;
if(dcmp(c4)==0 && InSegment(a2,b1,b2) ) return true;
return false;
}
bool PointInPolygon(Point p,Point *poly,int n)
{//poly点集大小==1或==2时也能正确运行
int wn=0;
for(int i=0;i<n;++i)
{
if(InSegment(p,poly[i],poly[(i+1)%n])) return true;
int k=dcmp(Cross(poly[(i+1)%n]-poly[i], p-poly[i]));
int d1=dcmp(poly[i].y-p.y);
int d2=dcmp(poly[(i+1)%n].y-p.y);
if(k>0 && d1<=0 && d2>0) wn++;
if(k<0 && d2<=0 && d1>0) wn--;
}
if(wn!=0) return true;
return false;
}
int ConvexHull(Point *p,int n,Point *ch)
{
sort(p,p+n);
n=unique(p,p+n)-p;
int m=0;
for(int 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];
}
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;
}
/***以上为刘汝佳模板***/
bool ConvexHullDivide(Point *p,int n,Point *q,int m)//判断p和q凸包是可以划分开
{
for(int i=0;i<n;++i)
if(PointInPolygon(p[i],q,m)) return false;
for(int i=0;i<m;i++)
if(PointInPolygon(q[i],p,n)) return false;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(SegmentIntersection(p[i],p[(i+1)%n],q[j],q[(j+1)%m])) return false;
return true;
}
const int maxn=500+5;
Point P[maxn],Q[maxn];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2 && n)
{
Point p[maxn],q[maxn];
for(int i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=0;i<m;i++)
scanf("%lf%lf",&q[i].x,&q[i].y);
n=ConvexHull(p,n,P);
m=ConvexHull(q,m,Q);
printf("%s\n",ConvexHullDivide(P,n,Q,m)?"Yes":"No");
}
return 0;
}
分享到:
相关推荐
The Divide-and-Conquer Strategy
For __ndelay we divide by 2^16, so the factor is multiplied by the same amount.
This file contains methods that provides the functionality.
Divide/Create data into training and testing data which are balanced basing on the labels.
Using BP algorithm to divide the data.This code can be used in other area as well
算法设计英文版课件:Chapter 4 The Divide-and-Conquer Strategy.ppt
Cellcom uses AgilePoint to automate the order process for landline communications and technical inquiries from clients, and to develop cross- functional processes across its existing billing and SAP ...
herein called the “great divide.” This book is worth buying for no other reason than simply to understand this “great divide” and its implications to the decision-making ability of the corporation...
计算器-iOS 计算器 :divide: 应用程序 实体模型(目前) 使用Swift / Storyboard进行构建,作为Swift学习课程的一部分 屏幕截图: 人像模式 风景模式 : : : : 应用程序图标:
这是用Verilog编写的除法模块(divide module),包括了divide程序设计模块和测试模块。
opencv 中关于 mat 矩阵的基本运算操作,有实例和注释,可以方便查看结果
JUnit测试代码,此文件为java工程文件,例子为整数除法。
根据该手册,可以配置LPm_divide.quartus自带的IP中除法器。可以配置为单时钟运行。或者多时钟运行。根据我的经验,要跑到到100M,需要20个时钟。
FPGA Verilog浮点数除法运算,采用单精度浮点型小数格式,运算结果精度可设置,可封装成IP核
a general method for solving divide and conquer recurrences
自己经常调用的FPGA分频程序
LCS匹配算法,divide and conquer LCS
java原始源码Divide.io 注意:主要开发人员目前已停止对该项目的开发。 我们将继续维护该项目,因此如果您有兴趣帮助开发,请参阅 。 Divide.io 是一个开源的后端即服务 (BaaS)。 它提供了在您的应用程序和服务器...
一款可以实现一次性出一个商或者两个商的除法器
CARRY LOOK AHEAD USING VERILOG