UVa 10256 (判断两个凸包相离) The Great Divide

题意:

给出n个红点,m个蓝点。问是否存在一条直线使得红点和蓝点分别分布在直线的两侧,这些点不能再直线上。

分析:

求出两种点的凸包,如果两个凸包相离的话,则存在这样一条直线。

判断凸包相离需要判断这两件事情:

  1. 任何一个凸包的任何一个顶点不能在另一个凸包的内部或者边界上。
  2. 两个凸包的任意两边不能相交。

二者缺一不可,第一条很好理解,但为什么还要判断第二条,因为存在这种情况:

UVa 10256 (判断两个凸包相离) The Great Divide

虽然每个凸包的顶点都在另一个凸包的外部,但两个凸包明显是相交的。

 //#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std; const int maxn = + ;
const double eps = 1e-;
const double PI = acos(-1.0); int dcmp(double x)
{
if(fabs(x) < eps) return ;
else return x < ? - : ;
} struct Point
{
double x, y;
Point(double x=, double y=):x(x), y(y) {}
};
typedef Point Vector;
Point operator + (Point a, Point b) { return Point(a.x+b.x, a.y+b.y); }
Point operator - (Point a, Point b) { return Point(a.x-b.x, a.y-b.y); }
Point operator * (Point a, double p) { return Point(a.x*p, a.y*p); }
Point operator / (Point a, double p) { return Point(a.x/p, a.y/p); }
bool operator < (Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
bool operator == (Point a, Point b) { return 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 SegmentIntersection(Point a1, Point a2, Point b1, Point 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);
return dcmp(c1*c2) < && dcmp(c3*c4) < ;
} bool OnSegment(Point p, Point a, Point b)
{//点是否在线段上,不包含在端点处的情况
return dcmp(Cross(a-p, b-p)) == && dcmp(Dot(a-p, b-p)) < ;
} vector<Point> ConvexHull(vector<Point> p)
{
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end()); int n = p.size();
int m = ;
vector<Point> ch(n+);
for(int i = ; i < n; ++i)
{
while(m > && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;
ch[m++] = p[i];
}
int k = m;
for(int i = n-; i >= ; --i)
{
while(m > k && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;
ch[m++] = p[i];
}
if(m > ) m--;
ch.resize(m);
return ch;
} int IsPointInPolygon(Point p, const vector<Point>& poly)
{
int wn = ;
int n = poly.size();
for(int i = ; i < n; ++i)
{
if(OnSegment(p, poly[i], poly[(i+)%n])) return -; //边界
int k = dcmp(Cross(poly[(i+)%n]-poly[i], p-poly[i]));
int d1 = dcmp(poly[i].y-p.y);
int d2 = dcmp(poly[(i+)%n].y-p.y);
if(k > && d1 <= && d2 > ) wn++;
if(k < && d2 <= && d1 > ) wn--;
}
if(wn) return ; //内部
return ; //外部
} bool ConvexPolygonDisjiont(const vector<Point> ch1, const vector<Point> ch2)
{
int c1 = ch1.size(), c2 = ch2.size();
for(int i = ; i < c1; ++i)
if(IsPointInPolygon(ch1[i], ch2) != ) return false;
for(int i = ; i < c2; ++i)
if(IsPointInPolygon(ch2[i], ch1) != ) return false;
for(int i = ; i < c1; ++i)
for(int j = ; j < c2; ++j)
if(SegmentIntersection(ch1[i], ch1[(i+)%c1], ch2[j], ch2[(j+)%c2])) return false;
return true;
} int main(void)
{
#ifdef LOCAL
freopen("10256in.txt", "r", stdin);
#endif int n, m;
while(scanf("%d%d", &n, &m) == )
{
if(!n && !m) break;
vector<Point> p1, p2;
double x, y;
for(int i = ; i < n; ++i)
{
scanf("%lf%lf", &x, &y);
p1.push_back(Point(x, y));
}
for(int i = ; i < m; ++i)
{
scanf("%lf%lf", &x, &y);
p2.push_back(Point(x, y));
}
if(ConvexPolygonDisjiont(ConvexHull(p1), ConvexHull(p2))) puts("Yes");
else puts("No");
} return ;
}

代码君

上一篇:智能家居系统 Home Assistant 系列 --介绍篇


下一篇:使用DS18B20设计温控系统