#include<bits/stdc++.h>
#define int long long
#define MAXN (int)1e5+5
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int x[MAXN],y[MAXN];
bool query(vector<array<int,2>> s){
int j=0;
while((s[0][0]==x[j]&&s[0][1]==y[j])||(s[1][0]==x[j]&&s[1][1]==y[j])){
j++;
}
int o=(s[1][0]-s[0][0])*(s[2][1]-s[1][1])-(s[2][0]-s[1][0])*(s[1][1]-s[0][1]),
o2=(s[1][0]-s[0][0])*(y[j]-s[1][1])-(x[j]-s[1][0])*(s[1][1]-s[0][1]);
return (abs(o+o2)==abs(o)+abs(o2));
}
void solve() {
int t,n,q;cin>>t>>n;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
x[n]=x[0];
y[n]=y[0];
cin>>q;
int z=0;
while(q--){
int a,b;cin>>a>>b;
a^=(t*z*z*z);
b^=(t*z*z*z);
int o=query({{x[0],y[0]},{x[1],y[1]},{a,b}}),
o2=query({{x[n/2],y[n/2]},{x[n/2+1],y[n/2+1]},{a,b}});
if(o==o2){
z+=o;
cout<<(o?"DA\n":"NE\n");continue;
}
int l=2,r=n/2,ans=1;
while(l<=r){
int s=(l+r)/2;
if(query({{x[s-1],y[s-1]},{x[s],y[s]},{a,b}})==o){
//cout<<x[s-1]<<' '<<y[s-1]<<' '<<x[s]<<' '<<y[s]<<'\n';
l=s+1;
ans=s;
}else{
r=s-1;
}
}
l=n/2+2,r=n;
int ans2=n/2+1;
while(l<=r){
int s=(l+r)/2;
if(query({{x[s-1],y[s-1]},{x[s],y[s]},{a,b}})==o2){
ans2=s;
l=s+1;
}else{
r=s-1;
}
}
r=ans+n-ans2;
//cout<<o<<' '<<r<<'\n';
if((o&&r>n/2)||(!o&&r<n/2)){z++;
cout<<"DA\n";
}else{
cout<<"NE\n";
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int32_t T=1;//cin>>T;
while(T--) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |