JSOI2018 战争 题解
假设A部落占领的点集为(A),B部落的为(B)。
则问题转换成，给你一个向量(v)。判断是否(exists ain A,b+v=a,(bin B))
则是否存在(a-b=v)
若我们可以处理出(a-b)的点集(C)。问题就转换成查询一个向量是否在一个凸包内。
我们将所有(B)中的点乘上(-1)。得到(B')。
然后处理出向量(A)和(B)的闵科夫斯基和。关于闵科夫斯基和
可以得到一个大凸包。
然后取最下面的点（如果右多个就取最左面的）作为极点。将其它点极交排序。然后就可以用二分找到所属于的三角形假设是( riangle ABO)，(O)为极点。只需要判断({underset{A-v}{ ightarrow}}和 underset{B-v}{ ightarrow})叉乘的结果 的正负就好了。
注意：闵科夫斯基和一定要去除共线的点。
/*
{
######################
# Author #
# Gary #
# 2020 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const double INF=1e18;
typedef pair<int,int> mp;
/*}
*/
const double pi=3.1415926535897932384626433832795;
const double eps=1e-10;
struct vec{
double x,y;
vec(){}
vec(double X,double Y){
x=X;
y=Y;
}
bool operator < (vec oth){
if(x!=oth.x) return x<oth.x;
return y<oth.y;
}
double operator * (vec oth){
return x*oth.y-oth.x*y;
}
vec operator - (vec oth){
return vec(x-oth.x,y-oth.y);
}
vec operator + (vec oth){
return vec(x+oth.x,y+oth.y);
}
bool operator != (vec oth){
return (abs(x-oth.x)>eps)||(abs(y-oth.y)>eps);
}
};
double angle(vec v){
if(v.y>=0){
if(abs(v.x)<=eps) return pi/2.0;
if(v.x>eps){
return atan(v.y/v.x);
}
else return atan(v.y/v.x)+pi;
}
if(abs(v.x)<=eps) return pi/2.0+pi;
if(v.x>eps){
return atan(v.y/v.x)+2.0*pi;
}
return atan(v.y/v.x)+pi;
}
bool cmp(vec A,vec B){
return angle(A)<angle(B);
}
vector<int> sta;
bool used[200000+20];
struct convex_hull{
vector<vec> v;
convex_hull(){}
convex_hull(vector<vec> points){
memset(used,0,sizeof(used));
sta.clear();
sta.PB(0);
sort(ALL(points));
rep(i,points.size()){
if(!i) continue;
while(sta.size()>1&&(points[sta.back()]-points[sta[sta.size()-2]])*(points[i]-points[sta.back()])<=0){
used[sta.back()]=0;
sta.POB();
}
used[i]=1;
sta.PB(i);
}
int tmp=sta.size();
rl(i,points.size()-1,0){
if(used[i]) continue;
while(sta.size()>tmp&&(points[sta.back()]-points[sta[sta.size()-2]])*(points[i]-points[sta.back()])<=0) sta.POB();
sta.PB(i);
}
for(auto it:sta) v.PB(points[it]);
v.POB();
}
convex_hull operator + (convex_hull oth){
vec ma=vec(INF,INF),mb=vec(INF,INF);
for(auto it:v){
if(it.y<ma.y){
ma=it;
}
else if(it.y==ma.y&&it.x<ma.x) ma=it;
}
for(auto it:oth.v){
if(it.y<mb.y){
mb=it;
}
else if(it.y==mb.y&&it.x<mb.x) mb=it;
}
ma=ma+mb;
vector<vec> nv;
rep(i,v.size()){
nv.PB(v[(i+1)%v.size()]-v[i]);
}
rep(i,oth.v.size()){
nv.PB(oth.v[(i+1)%oth.v.size()]-oth.v[i]);
}
sort(ALL(nv),cmp);
convex_hull ret;
vec now=vec(0,0);
for(auto it:nv){
ret.v.PB(now);
now=now+it;
}
for(auto & it:ret.v) it=it+ma;
return ret;
}
vec get_polar_point(){
vec ret=vec(INF,INF);
for(auto it:v){
if(it.y<ret.y) ret=it;
else if(it.y==ret.y&&it.x<ret.x) ret=it;
}
return ret;
}
};
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
vector<vec> points;
rb(i,1,n){
int x,y;
scanf("%d%d",&x,&y);
points.PB(vec(x,y));
}
convex_hull A(points);
points.clear();
rb(i,1,m){
int x,y;
scanf("%d%d",&x,&y);
x=-x;
y=-y;
points.PB(vec(x,y));
}
convex_hull B(points);
A=A+B;
A=convex_hull(A.v);
vec pp=A.get_polar_point();
for(auto &it:A.v){
it=it-pp;
}
vector<vec> oth;
for(auto it:A.v){
if(it!=vec(0,0)){
oth.PB(it);
}
}
sort(ALL(oth),cmp);
rb(i,1,q){
int x,y;
scanf("%d%d",&x,&y);
vec query=vec(x,y);
query=query-pp;
bool ok=false;
int is=upper_bound(ALL(oth),query,cmp)-oth.begin();
if(is==oth.size()){
if(abs(angle(oth.back())-angle(query))<=eps&&oth.back().x+eps>=query.x){
ok=true;
}
}
else{
if(is!=0){
vec u,d;
u=oth[is];
d=oth[is-1];
if((u-query)*(d-query)<=eps){
ok=true;
}
}
else{
if(abs(angle(oth[0])-angle(query))<=eps&&oth[0].x+eps>=query.x){
ok=true;
}
}
}
printf("%d
",ok);
}
return 0;
}