QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611014#5443. Security at Museumspengpeng_fudanWA 1ms3824kbC++235.7kb2024-10-04 18:48:282024-10-04 18:48:29

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 18:48:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2024-10-04 18:48:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll M=998244353;
struct vec{
    ll x,y;
    vec(ll _x=0,ll _y=0):x(_x),y(_y){};
    int qx(){//四一二三排序,按需修改
        if(x>=0&&y>=0)  return 2;
        if(x<0&&y>=0)   return 3;
        if(x<0&&y<0)    return 4;
        if(x>=0&&y<0)   return 1;
        return -1;
    }
    bool operator<(vec a){
        if(qx()!=a.qx())    return qx()<a.qx();
        else{
            ll p=x*a.y,q=y*a.x;
            if(p!=q)    return p>q;
            else if(a.y==0) return abs(x)>abs(a.x);
            else return abs(y)>abs(a.y);
        }
    }
    ll len2(){return x*x+y*y;}
    vec operator *(ll k){return {x*k,y*k};}
    vec operator +(vec a){return {x+a.x,y+a.y};}
    vec operator -(vec a){return {x-a.x,y-a.y};}
    ll operator *(vec a){return x*a.x+y*a.y;}
    ll operator ^(vec a){return x*a.y-y*a.x;}
    bool operator ==(vec a){return x==a.x&&y==a.y;}
    bool operator !=(vec a){return (x!=a.x||y!=a.y);}
};
bool on_line(vec a,vec b,vec c){//c在线段a,b上
    if(((c-a)*(c-b))<=0&&((c-a)^(c-b))==0)  return true;
    return false;
}
bool on_ray(vec a,vec v,vec c){	//c在射线a,v上
	if(((c-a)^v)==0&&((c-a)*v)>=0)	return true;
	return false;
}
int sgn(ll x){
    if(x==0)    return 0;
    if(x<0) return -1;
    if(x>0) return 1;
}
bool check_1_1(vec a,vec b,vec c,vec d){//线段a,b和线段c,d有交点为1 边界不算
    if(on_line(a,b,c)||on_line(a,b,d)||on_line(c,d,a)||on_line(c,d,b))  return false;
    return sgn((c-b)^(a-b))*sgn((d-b)^(a-b))<0&&sgn((a-d)^(c-d))*sgn((b-d)^(c-d))<0;
}
bool check_1_2(vec a,vec v,vec c,vec d){//射线a,v和线段c,d有交点为1
	if(on_ray(a,v,c)||on_ray(a,v,d))	return true;
	return sgn(v^(c-a))*sgn(v^(d-a))<0&&sgn((a-d)^(c-d))!=sgn(v^(c-d));
}
vec pot[210];
int n;
bool check_in_poly(vec x){
	int ans=0;
	for(int i=0;i<n;i++){
		int nxt=(i==n-1?0:i+1);
		if(on_line(pot[i]*2,pot[nxt]*2,x))	return true;
		if(((pot[i]-pot[nxt])^vec(1,0))==0)	continue;
		if(on_ray(x,vec(1,0),pot[i]*2))	ans+=(pot[i].y>pot[nxt].y);
		else if(on_ray(x,vec(1,0),pot[nxt]*2))	ans+=(pot[nxt].y>pot[i].y);
		else if(check_1_2(x,vec(1,0),pot[i]*2,pot[nxt]*2))	ans++;			
	}
	return ans&1;
}
void solve(void) {
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;pot[i]={x,y};
    }
    struct node{
        int u,v;
        bool operator<(const node a)const {
            return (pot[v]-pot[u])<(pot[a.v]-pot[a.u]);
        }
    };
    vector<node> mp;
    vector<vector<int>> flag(n+1,vector<int>(n+1,-1));
    auto check=[&](auto self,int u,int v)->bool {
        if(flag[u][v]!=-1)  return flag[u][v];
        int pz=-1;
        for(int i=0;i<n;i++){
            if(i==u||i==v)  continue;
            int nxt=(i==n-1?0:i+1);
            if(((pot[nxt]-pot[i])^(pot[v]-pot[u]))!=0&&check_1_1(pot[u],pot[v],pot[i],pot[nxt]))    return flag[u][v]=0;
            if(on_line(pot[u],pot[v],pot[i]))  pz=i;
        }       
        if(pz!=-1)  return flag[u][v]=(self(self,u,pz)|self(self,pz,v));
        return flag[u][v]=check_in_poly(pot[u]+pot[v]);
    };
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(check(check,i,j))    {
                mp.push_back({i,j}),mp.push_back({j,i});
            }
        }
    }
    sort(mp.begin(),mp.end());
    vector<node> re;
    int sz=mp.size();
    ll ans=0;
    auto rebuild=[&](vector<node> now)->void {
        int sz=now.size();
        vector<vector<int>> tpst(n+sz);
        vector<ll> pw3(n+sz),num(n+sz),n1(n+sz);
        vector<int> du(n+sz+1);
        for(int i=0;i<sz;i++){
            auto [u,v]=now[i];
            tpst[u].push_back(i+n);
            du[i+n]++;
            tpst[i+n].push_back(v);
            du[v]++;
        }       
        queue<int> qe;
        for(int i=0;i<n+sz;i++){
            if(du[i]==0)    qe.push(i);
        }
        while(!qe.empty()){
            int w=qe.front();qe.pop();
            if(w>=n)    {
                re.push_back(now[w-n]);
                ans=(ans-num[w]+n1[w])%M;
            }
            for(auto j:tpst[w]){
                du[j]--;
                if(j<n) {pw3[j]=(pw3[j]+pw3[w])%M;num[j]+=num[w];n1[j]++;}
                else {pw3[j]=(pw3[j]+pw3[w]*3+n1[w])%M;num[j]+=num[w]+n1[w];}
                if(du[j]==0)    qe.push(j);
            }
        }
    };
    for(int i=0;i<sz;i++){
        int lo=i;
        vector<node> now;
        while(lo<sz){
            vec v1=pot[mp[lo].v]-pot[mp[lo].u];
            vec v2=pot[mp[i].v]-pot[mp[i].u];
            if((v1^v2)==0&&(v1*v2)>=0)  {now.push_back(mp[lo]);lo++;}
            else break;
        }
        i=lo-1;
        rebuild(now);
    }
    // for(auto [x,y]:re)  cerr<<x<<' '<<y<<'\n';
    for(int i=0;i<n;i++){
        vector<ll> dp(sz);
        vector<ll> pre(n);
        auto check=[&](int x)->bool {
            if(pot[x].x>pot[i].x||(pot[x].x==pot[i].x&&pot[x].y<=pot[i].y))    return true;
            return false;
        };
        pre[i]=1;
        for(int j=0;j<sz;j++){  
            if(check(re[j].u)&&check(re[j].v)){
                dp[j]=pre[re[j].u];
                if(re[j].v==i)  ans=(ans+dp[j])%M;
                pre[re[j].v]=(pre[re[j].v]+dp[j])%M;
                // cerr<<re[j].u<<' '<<re[j].v<<' '<<dp[j]<<'\n';
            }
        }
    }
    cout<<(ans%M+M)%M<<'\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    while (_--) solve();

    return 0;
}

/*
7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

*/


/*
3
0 0
1 0
1 1

*/

/*
7
0 20
40 0
40 20
70 50
50 70
30 50
0 50


*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3536kb

input:

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

output:

56

result:

ok 1 number(s): "56"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

4
0 0
-10 0
-10 -10
0 -10

output:

11

result:

ok 1 number(s): "11"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

4
0 0
10 5
20 0
10 10

output:

7

result:

ok 1 number(s): "7"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

4
-100 -10
100 -10
100 10
-100 10

output:

11

result:

ok 1 number(s): "11"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3544kb

input:

7
0 0
10 10
20 0
30 11
20 22
10 11
0 22

output:

44

result:

ok 1 number(s): "44"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

10
0 0
10 10
20 0
30 10
40 0
40 21
30 11
20 21
10 11
0 21

output:

93

result:

ok 1 number(s): "93"

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 3536kb

input:

7
0 0
50 50
80 20
110 50
70 90
40 60
0 100

output:

50

result:

wrong answer 1st numbers differ - expected: '44', found: '50'