P6679 [COCI2019-2020#2] Zvijezda 题解

· · 题解

设 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;
}