QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625643 | #5443. Security at Museums | Wuyanru | WA | 0ms | 3740kb | C++14 | 4.2kb | 2024-10-09 20:11:00 | 2024-10-09 20:11:04 |
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]>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!=j&&xian(i,k,j)) f=0;
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: 0
Wrong Answer
time: 0ms
memory: 3740kb
input:
7 0 20 40 0 40 20 70 50 50 70 30 50 0 50
output:
52
result:
wrong answer 1st numbers differ - expected: '56', found: '52'