QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#611176 | #5443. Security at Museums | pengpeng_fudan | WA | 171ms | 4496kb | C++23 | 6.0kb | 2024-10-04 19:46:52 | 2024-10-04 19:46:52 |
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]);
};
// cerr<<check(check,0,3)<<'\n';
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(check(check,i,j)) {
cerr<<i<<' '<<j<<'\n';
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];
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]++;
// if(pw3[w]!=1) cerr<<now[w-n].u<<' '<<now[w-n].v<<'\n';
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;
}
/*
12
0 0
4 0
4 5
0 5
0 2
2 2
2 3
1 3
1 4
3 4
3 1
0 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
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: 1ms
memory: 3608kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3796kb
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: 3832kb
input:
4 -100 0 0 -100 100 0 0 100
output:
11
result:
ok 1 number(s): "11"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3496kb
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: 3612kb
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: 3628kb
input:
4 -100 -10 100 -10 100 10 -100 10
output:
11
result:
ok 1 number(s): "11"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
4 0 0 100 0 60 30 0 30
output:
11
result:
ok 1 number(s): "11"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
4 0 0 100 0 60 30 40 30
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 1ms
memory: 3800kb
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: 3572kb
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: 0
Accepted
time: 1ms
memory: 3640kb
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:
51
result:
ok 1 number(s): "51"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
10 0 500 -10 20 -350 350 -20 0 -350 -350 0 -20 350 -350 20 0 350 350 10 20
output:
93
result:
ok 1 number(s): "93"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
16 0 0 10 -5 20 0 30 15 40 0 45 10 40 20 25 30 40 40 30 45 20 40 10 25 0 40 -5 30 0 20 15 10
output:
247
result:
ok 1 number(s): "247"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
8 100 90 90 100 -90 100 -100 90 -100 -90 -90 -100 90 -100 100 -90
output:
247
result:
ok 1 number(s): "247"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
8 0 0 10 100 90 100 100 0 100 201 90 101 10 101 0 201
output:
31
result:
ok 1 number(s): "31"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
8 0 0 100 100 900 100 1000 0 1000 210 900 110 100 110 0 210
output:
31
result:
ok 1 number(s): "31"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
3 1000000 -1000000 1000000 1000000 -1000000 -1000000
output:
4
result:
ok 1 number(s): "4"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
4 1000000 -1000000 1000000 1000000 1 0 -1000000 -1000000
output:
7
result:
ok 1 number(s): "7"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
4 1000000 -1000000 1000000 1000000 0 1 -1000000 -1000000
output:
11
result:
ok 1 number(s): "11"
Test #25:
score: 0
Accepted
time: 169ms
memory: 4496kb
input:
200 -28269 899556 -52917 898443 -82904 896173 -112799 892903 -139901 889060 -167758 884227 -196328 878325 -220331 872613 -248497 865014 -277258 856229 -302321 847703 -331311 836799 -354953 827048 -381571 815109 -407788 802314 -431209 789973 -455810 776039 -479961 761338 -503639 745887 -529006 728115...
output:
982924531
result:
ok 1 number(s): "982924531"
Test #26:
score: 0
Accepted
time: 171ms
memory: 4448kb
input:
200 -28269 899556 -52917 898443 -82904 896173 -112799 892903 -139901 889060 -167758 884227 -196328 878325 -220331 872613 -248497 865014 -277258 856229 -302321 847703 -331311 836799 -354953 827048 -381571 815109 -407788 802314 -431209 789973 -455810 776039 -479961 761338 -503639 745887 -529006 728115...
output:
491462169
result:
ok 1 number(s): "491462169"
Test #27:
score: -100
Wrong Answer
time: 58ms
memory: 4468kb
input:
200 -1000000 0 -984589 0 -959090 -1000000 -939997 0 -920698 -1000000 -903689 0 -878269 -1000000 -856526 0 -835872 -1000000 -824921 0 -802874 -1000000 -775273 0 -762503 -1000000 -736648 0 -723628 -1000000 -700062 0 -677324 -1000000 -655520 0 -638093 -1000000 -616069 0 -596730 -1000000 -578522 0 -5610...
output:
932052893
result:
wrong answer 1st numbers differ - expected: '766756066', found: '932052893'