自动搬运

查看原文

来自洛谷，原作者为

	Lieyiqi AFO

搬运于2025-08-24 22:23:01，当前版本为作者最后更新于2023-12-28 13:45:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $A_i$ 表示输入多边形中的第 $i$ 个 $(\bmod{n})$ 点，$X$ 表示 Mirko 的查询点。如果 $\operatorname{ccw}(A_i,A_i+1,X)>0$，则在我们的多边形的第 $i$ 条边上写入 $1$，否则写入 $0$。

那么现在有一个问题，“是否存在一对相反的边，但它们都写有 $1$”。

显然，不能暴力对每个查询都检查每条边上写的内容，因为这将导致 $O(nq)$ 的算法复杂度。所以我们要创造一个高效的算法来解决这个问题。

不难看出，如果两条边上都写有 $1$，则它们之间的所有边（在一个方向上）也都写有 $1$。

另外的，只有当一段连续的 $1$ 的区间包含至少 $\dfrac{n}{2}+1$ 个元素时，答案才是 DA。这是显而易见的，因为在 $\dfrac{n}{2}+1$ 个连续的边中必定存在两条相对的边。现在，我们考虑一条任意的边及其相反边，并观察它们上写的值。如果它们都写有 $1$，则可以直接输出 DA。如果它们都写有 $0$，则可以直接输出 NE。如果其中一条边写有 $1$，另一条边写有 $0$，则我们可以将数组分为两部分，每部分以我们已检查的一条边开头。一部分的形式 111...000，另一部分的形式为 000...111。我们想在其中一部分找到最后一个 $1$，在另一部分找到第一个 $1$。这可以用二分搜索快速完成。现在，我们已经找到了一个连续的 $1$ 的区间的端点，并且可以检查条件是否成立。

时间复杂度：$O(\operatorname{q}\log{n})$。

// VS Code C/C++
#include<iostream>
#include<cmath>
#include<vector>

#define I using
#define AK namespace
#define NOIP std;
#define f1 first
#define s2 second
#define db double
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<b;i++)
I AK NOIP

typedef long long ll;
typedef pair<ll,ll> pll;

int n;
vector<pll> py;
ll x,y;

inline db cmp(pll a,pll b,pll c){
	return db(a.f1)*(b.s2-c.s2)+
	db(b.f1)*(c.s2-a.s2)+
	db(c.f1)*(a.s2-b.s2);
}

inline bool get(int i){
	return cmp(py[i],py[(i+1)%n],{x,y})>=0;
}

const string o[]={"NE","DA"};

inline int mj(int l,int r){
	int li=l,hi=r,mid;
	while(li!=hi){
		mid=(li+hi+1)/2;
		if(get(mid)==get(l)) li=mid;
		else hi=mid-1;
	}
	int ret=li-l+1;
	if(!get(l)) ret=n/2-ret;
	return ret;
}

inline bool solve(){
	int mid=n/2;
	int a=get(0);
	int b=get(mid);
	if(a==b) return a;
	return mj(0,mid-1)+mj(mid,n-1)>mid;
}
signed main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t>>n;
	FOR(i,0,n){
		cin>>x>>y;
		py.pb({x,y});
	}
	int q;
	ll da=0;
	cin>>q;
	FOR(i,0,q){
		cin>>x>>y;
		x^=da*da*da*t;
		y^=da*da*da*t;
		int ans=solve();
		da+=ans;
		cout<<o[ans]<<'\n';
	}
	return 0;
}