QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#333257 | #5442. Referee Without Red | grass8cow | WA | 0ms | 3924kb | C++17 | 2.6kb | 2024-02-19 19:17:41 | 2024-02-19 19:17:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define db long double
const db eps=1e-10;
int sgn(db x){
if(abs(x)<eps)return 0;
return (x>0)?1:-1;
}
struct no{
db x,y;
no(){x=y=0;}
no(db x_,db y_){x=x_,y=y_;}
no operator + (const no &a) const{return no(x+a.x,y+a.y);}
no operator - (const no &a) const{return no(x-a.x,y-a.y);}
no operator * (const db &a) const{return no(x*a,y*a);}
no operator / (const db &a) const{return no(x/a,y/a);}
inline int sb(){
if(sgn(x)==0)return sgn(y)>0;
return sgn(x)>0;
}
}a[210],z[210];
int n;
#define pi pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
struct ed{
no s,t;
ed(){}
ed(no s_,no t_){s=s_,t=t_;}
};
db cro(no a,no b){return a.x*b.y-a.y*b.x;}
db dot(no a,no b){return a.x*b.x+a.y*b.y;}
db sat(no a,no b,no c){return cro(b-a,c-a);}
no jd(ed a,ed b){
db S1=sat(a.s,a.t,b.s),S2=sat(a.s,a.t,b.t);
return (b.t*S1-b.s*S2)/(S1-S2);
}
int side(ed a,no b){return sgn(sat(a.s,a.t,b));}
db pos(no a,ed l){return dot(a-l.s,l.t-l.s);}
bool Qin(no A,no B){
ed l=ed(A,B);
vector<pair<db,int> >e;
for(int i=1;i<=n;i++){
int f1=side(l,a[i]),f2=side(l,a[i+1]);
if(f1==f2)continue;
e.pb(mp(pos(jd(l,ed(a[i],a[i+1])),l),f1-f2));
}
sort(e.begin(),e.end());int sz=e.size();
db L=pos(A,l),R=pos(B,l);
int su=0;
for(int i=0,j=0;i<sz;i=j){
j=i;
while(j<sz&&!sgn(e[i].F-e[j].F)){if(i<j)e[i].S+=e[j].S;j++;}
if(j==sz)break;
su+=e[i].S;
if(!su&&sgn(e[j].F-L)>0&&sgn(R-e[i].F)>0)return 0;
}
return 1;
}
const int mod=998244353;
int dp[310][2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%Lf%Lf",&a[i].x,&a[i].y),z[i]=a[i];
a[n+1]=a[1];
sort(z+1,z+n+1,[&](no a,no b){if(!sgn(a.x-b.x))return a.y<b.y;return a.x<b.x;});
vector<pi>eo;
for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)
if(Qin(z[i],z[j]))
eo.pb(mp(i,j)),eo.pb(mp(j,i));
sort(eo.begin(),eo.end(),[&](pi a,pi b){
no ta=z[a.S]-z[a.F],tb=z[b.S]-z[b.F];
if(ta.sb()!=tb.sb())return ta.sb()>tb.sb();
if(sgn(cro(ta,tb)))return cro(ta,tb)<0;
return pos(z[a.F],ed(z[a.F],z[a.S]))<pos(z[b.F],ed(z[a.F],z[a.S]));
});
int ans=0;
for(int o=1;o<=n;o++){
memset(dp,0,sizeof(dp));
dp[o][0]=1;
for(pi Q:eo){
int s=Q.F,t=Q.S;
(dp[t][1]+=dp[s][1])%=mod;
if(side(ed(z[o],z[t]),z[s]))(dp[t][1]+=dp[s][0])%=mod;
else if(sgn(dot(z[s]-z[o],z[s]-z[t]))<=0)(dp[t][0]+=dp[s][0])%=mod;
}
(ans+=dp[o][1])%=mod;
for(int j=1;j<=n;j++)if(o!=j&&(sgn(z[j].y-z[o].y)>0||!sgn(z[j].y-z[o].y)&&sgn(z[j].x-z[o].x)>0))(ans+=dp[j][0])%=mod;
}
return printf("%d",ans),0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3924kb
input:
2 4 4 1 2 3 4 3 4 1 2 1 2 4 1 4 3 3 2 3 9 1 8 1 1 8 1 1 8 1 1 8 8 8 8 8 8 8 1 1 1 1 8 8 8 1 1 1
output:
1
result:
wrong answer 1st numbers differ - expected: '96', found: '1'