大致题意:

    给你一个凸多边形A,和一个任意多边形B,判断B是否在A的内部

  先对A的点集建凸包,然后枚举B中的点,二分判断是否在A的内部。

  二分时可用叉积判断,详细见代码

  

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<time.h>
#include<cstdlib>
#include<cmath>
#include<list>
using namespace std;
#define MAXN 100100
#define eps 1e-9
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Fore(i,a,b) for(int i=a;i>=b;i--)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mkp make_pair
#define pb push_back
#define cr clear()
#define sz size()
#define met(a,b) memset(a,b,sizeof(a))
#define iossy ios::sync_with_stdio(false)
#define fre freopen
#define pi acos(-1.0)
#define inf 1e6+7
#define Vector Point
const int Mod=1e9+;
typedef unsigned long long ull;
typedef long long ll;
int dcmp(double x){
if(fabs(x)<=eps) return ;
return x<?-:;
}
struct Point{
double x,y;
Point(double x=,double y=):x(x),y(y) {}
bool operator < (const Point &a)const{
if(x==a.x) return y<a.y;
return x<a.x;
}
Point operator - (const Point &a)const{
return Point(x-a.x,y-a.y);
}
Point operator + (const Point &a)const{
return Point(x+a.x,y+a.y);
}
Point operator * (const double &a)const{
return Point(x*a,y*a);
}
Point operator / (const double &a)const{
return Point(x/a,y/a);
}
void read(){
scanf("%lf%lf",&x,&y);
}
void out(){
cout<<"debug: "<<x<<" "<<y<<endl;
}
bool operator == (const Point &a)const{
return dcmp(x-a.x)== && dcmp(y-a.y)==;
}
};
double Dot(Vector a,Vector b) {
return a.x*b.x+a.y*b.y;
}
double dis(Vector a) {
return sqrt(Dot(a,a));
}
double Cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
int ConvexHull(Point *p,int n,Point *ch){
int m=;
For(i,,n-) {
while(m> && Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
int k=m;
Fore(i,n-,){
while(m>k && Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
if(n>) m--;
return m;
}
int n1,n2,m;
Point p1[],p2[];
Point ch[];
bool check(Point tp){
if(Cross(tp-ch[],ch[]-ch[])>= || Cross(tp-ch[],ch[m-]-ch[])<=) return ;
int l=,r=m-;
int now=l;
while(l<=r) {
int mid=l+r>>;
if(Cross(ch[mid]-ch[],tp-ch[])>) l=mid+,now=mid;
else r=mid-;
}
return Cross(ch[(now+)%m]-ch[now],tp-ch[now])>;
}
void solve(){
cin>>n1;
For(i,,n1-) p1[i].read();
cin>>n2;
For(i,,n2-) p2[i].read();
sort(p1,p1+n1);
m=ConvexHull(p1,n1,ch);
int mk=;
For(i,,n2-) {
if(!mk) break;
if(!check(p2[i])) mk=;
}
if(mk) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main(){
// fre("in.txt","r",stdin);
int t=;
solve();
return ;
}

最新文章

  1. NDK环境搭建
  2. Subversion安装和使用
  3. PHP之数组遍历
  4. Netty高性能之道
  5. [Android文档翻译]设备兼容性
  6. 第七届蓝桥杯javaB组真题解析-分小组(第四题)
  7. Failed to sync Gradle project &#39;XX&#39;错误解决
  8. React 实践项目 (五)
  9. Docker安装入门 -- 应用镜像
  10. 使用cmd查看电脑连接过的wifi密码(一)
  11. ArcGIS Pro玩转BIM应用浅谈
  12. 1.5 pycharm使用
  13. html table标签
  14. Python多进程vs多线程
  15. 使用JavaScript缓存图片
  16. day57作业(包含data内容)
  17. MarkDownPad 专业汉化破解
  18. [HNOI2019]校园旅行(构造+生成树+动规)
  19. log4j的使用配置
  20. Linux系统级别能够打开的文件句柄的数file-max命令

热门文章

  1. zlib解压缩gzip
  2. jquery validate submitHandler 提交导致死循环
  3. linux下怎么查找文件
  4. JS数组---转及补充--
  5. Android Studio Gradle&#39;s dependency cache may be corrupt Re-download dependencies and sync project (requires network)
  6. python_继承.ziw
  7. JVM学习十三:JVM之堆分析
  8. 【LibreOJ】#6298. 「CodePlus 2018 3 月赛」华尔兹 BFS
  9. 基本控件文档-UITableView---iOS-Apple苹果官方文档翻译
  10. C - A New Function (整除分块 + 玄学优化)