QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#625616#5443. Security at MuseumsWuyanruWA 1ms3964kbC++144.2kb2024-10-09 20:06:292024-10-09 20:06:30

Judging History

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

  • [2024-10-09 20:06:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3964kb
  • [2024-10-09 20:06:29]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=998244353;
struct node
{
    int u,v;
    ld x,y;
}a[40001];
bool e[201][201];
bool vis[201];
int id[201];
ll dp[201][2];
ld x[201];
ld y[201];
int n,c;
inline bool type(int x,int y)
{
    if(y>0) return 0;
    if(y<0) return 1;
    return x<0;
}
inline ld cha(int a,int b,int c)
{
    return (x[b]-x[a])*(y[c]-y[a])-(y[b]-y[a])*(x[c]-x[a]);
}
inline bool xian(int a,int b,int c)
{
    if((x[a]>x[b])!=(x[b]>x[c])) return false;
    if((y[a]>y[b])!=(y[b]>y[c])) return false;
    return cha(a,b,c)==0;
}
inline bool ins(int a,int b,int u,int v)
{
    ld v1=cha(a,b,u),v2=cha(a,b,v);
    ld v3=cha(u,v,a),v4=cha(u,v,b);
    if(!v1||!v2||!v3||!v4) return false;
    return (v1>0)!=(v2>0)&&(v3>0)!=(v4>0);
}
inline ld dis(int a,int b)
{
    return sqrtl((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
inline ld get(int a,int b)
{
    ld C=(x[b]-x[a])/dis(a,b),ans=acos(C);
    if(y[a]<y[b]||(y[a]==y[b]&&x[b]>x[a])) return ans;
    return 2*acos(-1)-ans;
}
inline void Add(ll &a,ll b)
{
    a+=b;
    if(a>=mod) a-=mod;
}
inline ll run(int id)
{
    memset(dp,0,sizeof(dp));ll ans=0;
    for(int i=1;i<=c;i++)
    {
        if(vis[a[i].u]||vis[a[i].v]) continue;
        // printf("%d -> %d\n",a[i].u,a[i].v);
        if(a[i].u==id) Add(dp[a[i].v][0],1),Add(ans,1);
        else if(a[i].v==id) Add(ans,dp[a[i].u][1]);
        else if(xian(id,a[i].u,a[i].v)) Add(ans,dp[a[i].u][0]),Add(dp[a[i].v][0],dp[a[i].u][0]);
        else if(xian(id,a[i].v,a[i].u)) Add(dp[a[i].v][0],dp[a[i].u][0]),Add(dp[a[i].v][1],dp[a[i].u][1]);
        else Add(dp[a[i].v][1],dp[a[i].u][0]),Add(dp[a[i].v][1],dp[a[i].u][1]);
    }
    vis[id]=1;
    // printf("id=%d : %lld\n",id,ans);
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j)
    {
        if(i%n+1==j||j%n+1==i){ e[i][j]=1;continue;}
        bool f=1;
        for(int k=1;k<=n;k++)
        {
            if(k==i||k%n+1==i) continue;
            if(k==j||k%n+1==j) continue;
            if(ins(i,j,k,k%n+1)) f=0;
        }
        if(!f) continue;
        int lt=(i+n-2)%n+1,nx=i%n+1;
        if(xian(i,lt,j)||xian(i,nx,j)) continue;
        ld v1=get(i,lt),v2=get(i,j),v3=get(i,nx);
        // printf("i=%d j=%d : %d %d : %Lf %Lf %Lf\n",i,j,lt,nx,v1,v2,v3);
        if(v2<v3) v2+=2*acos(-1);
        if(v1<v3) v1+=2*acos(-1);
        if(v2<v1) e[i][j]=1;
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&!e[i][j])
    {
        int lt=(i+n-2)%n+1,nx=i%n+1;
        if(xian(i,lt,j)) e[i][j]=e[lt][j];
        if(xian(i,nx,j)) e[i][j]=e[nx][j];
    }
    // for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",e[i][j]," \n"[j==n]);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(e[i][j])
    {
        c++;
        a[c].u=i,a[c].v=j;
        a[c].x=x[j]-x[i],a[c].y=y[j]-y[i];
    }
    sort(a+1,a+c+1,[](node a,node b) -> bool
    {
        bool v1=type(a.x,a.y),v2=type(b.x,b.y);
        if(v1!=v2) return v1<v2;
        ld p=a.x*b.y-a.y*b.x;
        if(p) return p>0;
        if(y[a.u]!=y[b.u]) return (y[a.u]<y[b.u])^v1;
        return (x[a.u]<x[b.u])^v1;
    });

    // for(int i=1;i<=c;i++) printf("%2d : %d -> %d\n",i,a[i].u,a[i].v);

    for(int i=1;i<=n;i++) id[i]=i;
    sort(id+1,id+n+1,[](int a,int b)
    {
        if(y[a]!=y[b]) return y[a]<y[b];
        return x[a]<x[b];
    });

    ll ans=0;
    for(int i=1;i<=n;i++) ans+=run(id[i]);
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3908kb

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

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: 3852kb

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: 3864kb

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: 3844kb

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: 3964kb

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: 3844kb

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: 3780kb

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: 3900kb

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: 3908kb

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: 3776kb

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: 3868kb

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: 3932kb

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:

66

result:

wrong answer 1st numbers differ - expected: '51', found: '66'