uva 10256 The Great Divide

时间:2021-07-05 22:38:26

题意:给定两个点集,一个红点集,另一个蓝点集,询问,能否找到一条直线能,使得任取一个红点和蓝点都在直线异侧。

思路:划分成两个凸包,一个红包,一个蓝包。两个凸包不相交不重合。

1.任取一个凸包中的点不在另一个凸包中。

2.任取一个凸包中的边与另一个凸包不相交。

 #include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<memory.h>
#include<cstdlib>
#include<vector>
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long int
#define up(i,x,y) for(i=x;i<=y;i++)
#define w(a) while(a)
using namespace std;
const double inf=0x3f3f3f3f;
const int N = ;
const double eps = *1e-;
const double PI = acos(-1.0); double 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; Vector operator - (const Point& A, const Point& B)
{
return Vector(A.x-B.x, A.y-B.y);
} double Cross(const Vector& A, const Vector& B)
{
return A.x*B.y - A.y*B.x;
} double Dot(const Vector& A, const Vector& B)
{
return A.x*B.x + A.y*B.y;
} bool operator < (const Point& p1, const Point& p2)
{
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
} bool operator == (const Point& p1, const Point& p2)
{
return p1.x == p2.x && p1.y == p2.y;
} bool SegmentProperIntersection(const Point& a1, const Point& a2, const Point& b1, const 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)< && dcmp(c3)*dcmp(c4)<;
} bool OnSegment(const Point& p, const Point& a1, const Point& a2)
{
return dcmp(Cross(a1-p, a2-p)) == && dcmp(Dot(a1-p, a2-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(n > ) m--;
ch.resize(m);
return ch;
} int IsPointInPolygon(const Point& p, const vector<Point>& poly)
{
int wn = ;
int n = poly.size();
for(int i = ; i < n; i++)
{
const Point& p1 = poly[i];
const Point& p2 = poly[(i+)%n];
if(p1 == p || p2 == p || OnSegment(p, p1, p2)) return -; // 在边界上
int k = dcmp(Cross(p2-p1, p-p1));
int d1 = dcmp(p1.y - p.y);
int d2 = dcmp(p2.y - p.y);
if(k > && d1 <= && d2 > ) wn++;
if(k < && d2 <= && d1 > ) wn--;
}
if (wn != ) return ; // 内部
return ; // 外部
} bool ConvexPolygonDisjoint(const vector<Point> ch1, const vector<Point> ch2)
{
int c1 = ch1.size();
int 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(SegmentProperIntersection(ch1[i], ch1[(i+)%c1], ch2[j], ch2[(j+)%c2])) return false;
return true;
} int main()
{
int n, m;
while(scanf("%d%d", &n, &m) == && n > && m > )
{
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(ConvexPolygonDisjoint(ConvexHull(P1), ConvexHull(P2)))
printf("Yes\n");
else
printf("No\n");
}
return ;
}

uva 10256 The Great Divide的更多相关文章

  1. UVA 10256 The Great Divide&lpar;凸包划分&rpar;

    The Great Divide Input: standard input Output: standard output Time Limit: 8 seconds Memory Limit: 3 ...

  2. UVa 10256 - The Great Divide 判断凸包相交

    模板敲错了于是WA了好几遍…… 判断由红点和蓝点分别组成的两个凸包是否相离,是输出Yes,否输出No. 训练指南上的分析: 1.任取红凸包上的一条线段和蓝凸包上的一条线段,判断二者是否相交.如果相交( ...

  3. UVA 10256 The Great Divide (凸包,多边形的位置关系)

    题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34148 [思路] 凸包 求出红蓝点的凸包,剩下的问题就是判断两个凸 ...

  4. UVa 10256 The Great Divide,推断两个凸包是否相离

    先从给出的两个点集中分别计算出两个凸包, 然后推断两个凸包是否相离. #include<cstdio> #include<vector> #include<cmath&g ...

  5. UVA&Tab;10256 The Great Divide&lpar;点在多边形内&rpar;

    The Great Divid [题目链接]The Great Divid [题目类型]点在多边形内 &题解: 蓝书274, 感觉我的代码和刘汝佳的没啥区别,可是我的就是wa,所以贴一发刘汝佳 ...

  6. UVA - 10375 Choose and divide&lbrack;唯一分解定理&rsqb;

    UVA - 10375 Choose and divide Choose and divide Time Limit: 1000MS   Memory Limit: 65536K Total Subm ...

  7. 【暑假】&lbrack;数学&rsqb;UVa 10375 Choose and divide

    UVa 10375 Choose and divide 题目: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19601 思路 ...

  8. UVa 10256 &lpar;判断两个凸包相离&rpar; The Great Divide

    题意: 给出n个红点,m个蓝点.问是否存在一条直线使得红点和蓝点分别分布在直线的两侧,这些点不能再直线上. 分析: 求出两种点的凸包,如果两个凸包相离的话,则存在这样一条直线. 判断凸包相离需要判断这 ...

  9. UVa 10256 凸包简单应用

    题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem& ...

随机推荐

  1. http请求过程简要

    一次http请求主要分为3个大步. 建立tcp连接. 这里就发生了经典的tcp三次握手.做个类比解释下,tcp好比http的秘书,和厂家(服务器端)做买卖.老板(http)叫秘书(tcp)去联系一下, ...

  2. SVN学习之svn命令行下的基本操作

    http://huihai.iteye.com/blog/1985751 上一节已经把svn安装完成,下来就用命令行做一些简单的操作. 1.当svn安装完成后,svn管理人员会在svn的root根目录 ...

  3. Linux服务器指令

    1.查看cpu信息:/proc/cpuinfo2.查看内存信息:/prco/meminfo3.查看服务器版本信息:cat /etc/issue4.服务器系统位数:uname -a5.网卡信息:ifco ...

  4. USART笔记 基于STM32F107VCT6

    USART   通用同步异步收发器 通用同步异步收发器(USART)提供了一种灵活的方法与使用工业标准NRZ异步串行数据格式的外部设备之间进行全双工数据交换.USART利用分数波特率发生器提供宽范围的 ...

  5. &OpenCurlyDoubleQuote;假如花千骨在杭州拍摄” 主题Cosplay

    “假如花千骨在杭州拍摄” 主题Cosplay 今天,2015年7月23日,本周三:此刻,现场正在中国杭州西湖举办“花千骨cosplay”大型分享活动,现场有超凡而孤高,冰凉而淡漠 ,温润如玉又云淡风清 ...

  6. hdu 2841 Visible Trees

    /** 大意: 求[1,m], [1,n] 之间有多少个数互素...做了 1695 ,,这题就so easy 了 **/ #include <iostream> #include < ...

  7. audiounit错误码对应值查询

    https://www.osstatus.com/search/results?platform=all&framework=all&search=(错误码的值) EX:  https ...

  8. CentOS7 上学习使用docker

    一.CentOS7(64)上安装和使用docker的笔记. 1. 增加docker用户 sudo groupadd docker sudo useradd -g docker docker 2. 增加 ...

  9. POJ3662或洛谷1948 Telephone Lines

    二分答案+单源最短路 POJ原题链接 洛谷原题链接 显然可以二分答案,检验\(mid\)可以使用最短路来解决. 将大于\(mid\)的边看成长度为\(1\)的边,说明要使用免费升级服务,否则长度为\( ...

  10. python-day5笔记

    一.python基础--基本数据类型 (无论用户输入什么内容,input 都会存成字符串格式) 1.基本数据类型 1)数字类型 整型(整数)int:年级,年纪,等级,身份证号,QQ号,手机号,leve ...