QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#625537 | #5443. Security at Museums | Wuyanru | WA | 1ms | 3924kb | C++14 | 3.9kb | 2024-10-09 19:40:38 | 2024-10-09 19:40:38 |
Judging History
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]+y[a])>(x[b]+y[b]))!=((x[b]+y[b])>(x[c]+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;
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;
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++) 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;
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3920kb
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: 3920kb
input:
3 0 2022 -2022 -2022 2022 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 4 0 0 3 0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
3 -10 0 10 0 0 18
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3872kb
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: 3840kb
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: 3716kb
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: 3868kb
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: 3800kb
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: 3716kb
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: 3848kb
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: 0ms
memory: 3844kb
input:
7 0 0 10 10 20 0 30 11 20 22 10 11 0 22
output:
42
result:
wrong answer 1st numbers differ - expected: '44', found: '42'