社区讨论

60分,调了一天,悬赏5r,2关注,求调

P4557[JSOI2018] 战争参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo23qi8v
此快照首次捕获于
2023/10/23 07:30
2 年前
此快照最后确认于
2023/11/03 07:50
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define ll long long 
#define lf long double 
using namespace std;
const int N = 5e5 + 10;
const lf eps = 1e-7;
int n, m, q;
int s[N], top, tot = 0;
int l,r,mid;
ll x,y;
lf ra,rb;
struct Vec{
	ll x,y;
	Vec operator +(const Vec a)const{
		return (Vec){x + a.x,y + a.y};
	}
	Vec operator -(const Vec a)const{
		return (Vec){x - a.x,y - a.y};
	}
	ll operator *(const Vec a)const{
		return x * a.y - y * a.x;
	}
	ll _abs()const{
		return x * x + y * y; 
	}
	bool operator <(const Vec b)const{
		ra = atan2(y,x);
		rb = atan2(b.y,b.x);
		if(ra * rb < -eps){
			return ra - rb > eps;
		}else{
			return ra - rb < eps; 
		}
	}
}a[N],b[N],ans[N],an[N],qu,fi;
bool cmp(Vec a, Vec b, Vec f){
	if((a - f) * (b - f) > 0) return 1;
	else if((b - f) * (a - f) == 0) return (b - f)._abs() < (a - f)._abs();
	else return 0;
}
void tb(Vec p[],int n){
	top = 0;
	for(int i = 1; i <= n; ++i){
		if(p[i].y < p[1].y || 
		(p[i].y - p[1].y == 0 && p[i].x < p[1].x)){
			swap(p[1],p[i]);
		}
	}
	auto icmp = [&](Vec a, Vec b) {
		return cmp(a, b, p[1]);
	};
	sort(p + 2, p + 1 + n, icmp);
	for(int i = 1; i <= n; ++i){
		while(top >= 2 && ((p[s[top]]) - p[s[top - 1]]) * ((p[i]) - p[s[top]]) < 0) 
			--top;
		s[++top] = i;
	}
	s[top + 1] = 1;
	for(int i = 1; i <= top; ++i){
		ans[++tot] = (p[s[i + 1]] - p[s[i]]);
	}
}
void tbb(Vec p[],int n){
	top = 0;
	for(int i = 1; i <= n; ++i){
		if(p[i].y < p[1].y || 
		(p[i].y - p[1].y == 0 && p[i].x < p[1].x)){
			swap(p[1],p[i]);
		}
	}
	auto icmp = [&](Vec a, Vec b) {
		return cmp(a, b, p[1]);
	};
	sort(p + 2, p + 1 + n, icmp);
	for(int i = 1; i <= n; ++i){
		while(top >= 2 && ((p[s[top]]) - p[s[top - 1]]) * ((p[i]) - p[s[top]]) < 0) 
			--top;
		s[++top] = i;
	}
	s[top + 1] = 1;
	for(int i = 1; i <= top; ++i){
		an[i] = ans[s[i]];
	}
}
void input(){
	cin>>n>>m>>q;
	for(int i = 1; i <= n; ++i)
		cin>> a[i].x >> a[i].y;
	tb(a, n);
	for(int i = 1; i <= m; ++i){
		cin>> b[i].x >> b[i].y;
		b[i].x = -b[i].x;
		b[i].y = -b[i].y;
	}
	tb(b, n);
}
void pre(){
	sort(ans + 1, ans + 1 + tot);
	for(int i = 1; i <= tot; ++i){
		ans[i] = ans[i - 1] + ans[i];
	}
	tbb(ans,tot);
}
void op(){
	for(int i = 1; i <= q; ++i){
		cin>> qu.x >> qu.y;
		qu = qu - a[1] - b[1];
		if(qu * an[2] > 0 || qu * an[tot] < 0){
			cout<<0<<'\n';
			continue;
		} 
		l = 2,r = tot;
		while(l < r){
			mid = (l + r) >> 1;
			if(qu * an[mid] >= 0) r = mid;
			else l = mid + 1;
		}
		if((an[l - 1] - qu) * (an[l] - qu) >= 0){
			cout<<1<<'\n';
		}else{
			cout<<0<<'\n';
		}
	}
}
int main(){
    input();
    pre();
    op();
	return 0;
}
/*
3 3 1
4 -1
0 0
0 -2
0 -1
1 -2
-1 -3
-2 1
*/

回复

0 条回复,欢迎继续交流。

正在加载回复...