QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333257#5442. Referee Without Redgrass8cowWA 0ms3924kbC++172.6kb2024-02-19 19:17:412024-02-19 19:17:42

Judging History

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

  • [2024-02-19 19:17:42]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3924kb
  • [2024-02-19 19:17:41]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'