QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611132 | #5443. Security at Museums | pengpeng_fudan | WA | 1ms | 3800kb | C++23 | 6.0kb | 2024-10-04 19:33:38 | 2024-10-04 19:33:43 |
Judging History
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;
}
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%M;
a=a*a%M;
b>>=1;
}
return ans;
}
const ll inv_2=qpow(2,M-2);
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);
vector<int> du(n+sz+1);
for(int i=0;i<sz;i++){
auto [u,v]=now[i];
// cerr<<u<<' '<<v<<"\n";
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) {
pw3[w]++,num[w]++;
re.push_back(now[w-n]);
ans=(ans-pw3[w]+num[w]%M)%M;
}
for(auto j:tpst[w]){
du[j]--;
// cerr<<"!!!"<<w<<' '<<j<<'\n';
if(j<n) {pw3[j]=(pw3[j]+pw3[w])%M;num[j]+=num[w];}
else {pw3[j]=(pw3[j]+pw3[w]*3)%M;num[j]+=num[w];}
if(du[j]==0) qe.push(j);
}
}
// cerr<<'\n';
};
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);
}
ans=ans*inv_2%M;
// 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 0
50 50
80 20
110 50
70 90
40 60
0 100
*/
/*
3
0 0
1 0
1 1
*/
/*
7
0 20
40 0
40 20
70 50
50 70
30 50
0 50
*/
/*
4
0 0
1 0
2 0
3 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3532kb
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: 3540kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
4 0 0 -10 0 -10 -10 0 -10
output:
11
result:
ok 1 number(s): "11"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3544kb
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: 3540kb
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: 3800kb
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: 3780kb
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: 3608kb
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: 3624kb
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: 3556kb
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: 1ms
memory: 3548kb
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: 0
Accepted
time: 0ms
memory: 3556kb
input:
7 0 0 50 50 80 20 110 50 70 90 40 60 0 100
output:
44
result:
ok 1 number(s): "44"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
16 0 0 20 0 20 10 40 10 40 20 60 20 60 30 70 30 70 40 50 40 50 30 30 30 30 20 10 20 10 10 0 10
output:
407
result:
ok 1 number(s): "407"
Test #16:
score: -100
Wrong Answer
time: 1ms
memory: 3552kb
input:
12 0 0 400 0 400 500 0 500 0 200 200 200 200 300 100 300 100 400 300 400 300 100 0 100
output:
118
result:
wrong answer 1st numbers differ - expected: '51', found: '118'