QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558628 | #5443. Security at Museums | ucup-team052 | WA | 0ms | 3832kb | C++23 | 3.8kb | 2024-09-11 17:12:50 | 2024-09-11 17:12:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y) {return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y) {return 1ULL*x*y%mod;}
using db=long double;
const db eps=1e-9;
int sgn(db x)
{
if(x<-eps) return -1;
else if(x>eps) return 1;
else return 0;
}
struct Vec{
db x,y;
Vec(db a=0,db b=0) {x=a,y=b;}
db norm() {return x*x+y*y;}
db abs() {return sqrt(x*x+y*y);}
db arg() const { return atan2(y, x); }
};
Vec operator + (Vec x,Vec y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (Vec x,Vec y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (Vec x,db y) {return Vec(x.x*y,x.y*y);}
Vec operator / (Vec x,db y) {return Vec(x.x/y,x.y/y);}
db cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
db cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int ccw(const Vec &x,const Vec &y,const Vec &z) {return sgn(cross(y-x,z-x));}
int half(Vec v) {return v.y<0||(v.y==0&&v.x<0);}
int cmp(Vec x,Vec y){
return half(x)==half(y)?cross(x,y)>0:half(y);
}
struct Seg
{
Vec s,t;
Seg() {}
Seg(Vec p,Vec q) {s=p,t=q;}
int onseg(Vec o)
{
return sgn(cdot(o-s,o-t))<=0&&sgn(cross(o-s,o-t))==0;
}
};
int intersect(Seg p,Seg q) // strict intersect
{
return ccw(p.s,p.t,q.s)*ccw(p.s,p.t,q.t)==-1&&ccw(q.s,q.t,p.s)*ccw(q.s,q.t,p.t)==-1;
}
Vec crosspoint(Seg p,Seg q)
{
db A=cross(p.t-p.s,q.t-q.s);
db B=cross(p.t-p.s,p.t-q.s);
return q.s+(q.t-q.s)*(B/A);
}
bool seginpolygon(const vector<Vec> &a,int i,int j){
auto chkin=[&](Vec O,Vec P,Vec Q,Vec R)
{
if(ccw(O,P,Q)==1) return ccw(O,P,R)>=0&&ccw(O,R,Q)>=0;
else return !(ccw(O,Q,R)==1&&ccw(O,R,P)==1);
};
int n=a.size();
if(!chkin(a[i],a[(i+1)%n],a[(i-1+n)%n],a[j])) return 0;
if(!chkin(a[j],a[(j+1)%n],a[(j-1+n)%n],a[i])) return 0;
int ok=1; Seg cur(a[i],a[j]);
for(int k=0;k<n;k++) if(intersect(cur,Seg(a[k],a[(k+1)%n]))) ok=0;
if(!ok) return 0;
for(int k=0;k<n;k++)
{
if(k==i||k==j) continue;
if(cur.onseg(a[k]))
{
if(!chkin(a[k],a[(k+1)%n],a[(k-1+n)%n],a[i])) ok=0;
if(!chkin(a[k],a[(k+1)%n],a[(k-1+n)%n],a[j])) ok=0;
}
}
return ok;
}
#define N 205
Vec a[N];
vector<Vec> all;
int n;
struct Edge{
int i,j;
Vec get() {return a[j]-a[i];}
};
bool cmpseg(Edge x,Edge y){
Vec A=x.get(),B=y.get();
if(!cmp(A,B)&&!cmp(B,A)) return cdot(a[x.i],A)<cdot(a[y.i],A);
else return cmp(A,B);
}
vector<Edge> edges;
int ans;
int f[N],pw4[N],pw2[N];
signed main()
{
#ifdef xay5421
freopen("b.in","r",stdin);
#endif
pw4[0]=1; for(int i=1;i<N;i++) pw4[i]=mul(pw4[i-1],4);
pw2[0]=1; for(int i=1;i<N;i++) pw2[i]=mul(pw2[i-1],2);
cin>>n; for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
all=vector<Vec>(a,a+n);
for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j)
{
if(seginpolygon(all,i,j)) edges.push_back({i,j});
}
sort(edges.begin(),edges.end(),cmpseg);
// for(auto [x,y]:edges) printf("%d %d\n",x,y);
for(int i=0;i<n;i++)
{
memset(f,0,sizeof(f));
f[i]=1;
for(auto [x,y]:edges)
{
f[y]=add(f[y],f[x]);
}
ans=add(ans,f[i]);
// cout<<i<<" "<<f[i]<<endl;
}
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
{
Seg s(a[i],a[j]);
int cnt=0;
for(int k=0;k<n;k++) if(k!=i&&k!=j) cnt+=s.onseg(a[k]);
ans=sub(ans,pw4[cnt]);
ans=add(ans,pw2[cnt]);
}
cout<<sub(ans,n)<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
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: 3808kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3808kb
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: 3828kb
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: 3804kb
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: 3716kb
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: 3712kb
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: 3720kb
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: 3832kb
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: 3692kb
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: -100
Wrong Answer
time: 0ms
memory: 3808kb
input:
10 0 0 10 10 20 0 30 10 40 0 40 21 30 11 20 21 10 11 0 21
output:
89
result:
wrong answer 1st numbers differ - expected: '93', found: '89'