QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#152389 | #5443. Security at Museums | TadijaSebez | WA | 1ms | 3788kb | C++14 | 3.1kb | 2023-08-28 06:23:19 | 2023-08-28 06:23:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
void ckadd(int&x,int y){x=add(x,y);}
void cksub(int&x,int y){x=sub(x,y);}
struct pt{
ll x,y;
pt(){}
pt(ll a,ll b):x(a),y(b){}
};
pt operator - (const pt& a,const pt& b){
return pt(a.x-b.x,a.y-b.y);
}
ll cross(const pt& a,const pt& b){
return a.x*b.y-a.y*b.x;
}
ll dot(const pt& a,const pt& b){
return a.x*b.x+a.y*b.y;
}
int part(const pt& a){
if(a.y<0 || (a.y==0 && a.x<0))return 0;
else return 1;
}
const int N=205;
pt a[N];
bool valid[N][N];
int sgn(ll x){return x==0?0:x<0?-1:1;}
bool intersect(pt A,pt B,pt C,pt D){
int sa=sgn(cross(D-C,A-C));
int sb=sgn(cross(D-C,B-C));
int sc=sgn(cross(B-A,C-A));
int sd=sgn(cross(B-A,D-A));
if(sa*sb==1)return false;
if(sc*sd==1)return false;
if(sa*sb==-1){
if(sd*sc==-1)return true;
if(sd==1){
if(sc==0){
ll dotA=dot(B-A,A);
ll dotB=dot(B-A,B);
ll dotC=dot(B-A,C);
if(dotA<=dotC && dotC<=dotB){
return true;
}
}
}
}else if(sb==-1){
if(sa==0){
return true;
}
}
return false;
}
bool Check(int n,int p,int q){
auto next=[&](int i){return i==n?1:i+1;};
for(int f=0;f<2;f++){
int p1=next(p);
while(p1!=q && cross(a[p1]-a[p],a[q]-a[p])==0){
p1=next(p1);
}
if(p1==q)return true;
if(cross(a[p1]-a[p],a[q]-a[p])<0)return false;
p1=next(p);
int p0=p;
while(p1!=q){
if(p0!=p && intersect(a[p],a[q],a[p0],a[p1])){
return false;
}
p0=p1;
p1=next(p1);
}
swap(p,q);
}
return true;
}
struct Event{
pt dir;
int i,j;
Event(pt d,int a,int b):dir(d),i(a),j(b){}
bool operator < (const Event& other) const {
int pa=part(dir);
int pb=part(other.dir);
if(pa!=pb)return pa<pb;
ll c=cross(dir,other.dir);
if(c!=0)return c<0;
return dot(dir,a[i])<dot(dir,a[other.i]);
}
};
int dp[N][N];
int main(){
int n;
scanf("%i",&n);
for(int i=1;i<=n;i++){
scanf("%lld %lld",&a[i].x,&a[i].y);
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
valid[i][j]=valid[j][i]=Check(n,i,j);
}
}
vector<Event> evs;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(valid[i][j]){
evs.pb(Event(a[j]-a[i],i,j));
}
}
}
sort(evs.begin(),evs.end());
for(int i=1;i<=n;i++){
dp[i][i]=1;
}
for(const Event& ev:evs){
for(int i=1;i<=n;i++){
ckadd(dp[i][ev.j],dp[i][ev.i]);
}
}
int ans=0;
for(int i=1;i<=n;i++){
ckadd(ans,sub(dp[i][i],1));
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(valid[i][j]){
int sb=1,ad=1;
pt dir=a[j]-a[i];
ll dotA=dot(dir,a[i]);
ll dotB=dot(dir,a[j]);
for(int z=1;z<=n;z++){
if(z!=i && z!=j){
if(cross(a[i]-a[z],a[j]-a[z])==0){
ll dotC=dot(dir,a[z]);
if(dotA<dotC && dotC<dotB){
sb=mul(sb,4);
ad=mul(ad,2);
}
}
}
}
cksub(ans,sb);
ckadd(ans,ad);
}
}
}
printf("%i\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
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: 3616kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3660kb
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: 3680kb
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: 3788kb
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: 3788kb
input:
4 0 0 20 0 30 10 10 10
output:
11
result:
ok 1 number(s): "11"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3656kb
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: 3724kb
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: 3656kb
input:
4 0 0 100 0 60 30 40 30
output:
11
result:
ok 1 number(s): "11"
Test #12:
score: -100
Wrong Answer
time: 1ms
memory: 3700kb
input:
7 0 0 10 10 20 0 30 11 20 22 10 11 0 22
output:
39
result:
wrong answer 1st numbers differ - expected: '44', found: '39'