社区讨论
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 条回复,欢迎继续交流。
正在加载回复...