QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134557#4942. Robust DefensePhantomThresholdTL 3653ms7164kbC++204.4kb2023-08-03 23:39:422023-08-03 23:39:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 23:39:43]
  • 评测
  • 测评结果:TL
  • 用时:3653ms
  • 内存:7164kb
  • [2023-08-03 23:39:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long db;
const db eps=0;
int sign(db k){
	if (k>eps) return 1;
	else if (k<-eps) return -1;
	return 0;
}
int cmp(db k1,db k2){
	return sign(k1-k2);
}
int inmid(db k1,db k2,db k3){
	return sign(k1-k3)*sign(k2-k3)<=0;
}
 
struct point{
	db x,y;
	point operator + (const point &k1){return (point){x+k1.x,y+k1.y};}
	point operator - (const point &k1){return (point){x-k1.x,y-k1.y};}
	point operator * (db k1){return (point){x*k1,y*k1};}
	point operator / (db k1){return (point){x/k1,y/k1};}
	
	int operator == (const point &k1){
		return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;
	}
	
	db abs(){return hypot(x,y);}
	db abs2(){return x*x+y*y;}
	db dis(point k1){return ((*this)-k1).abs();}
	
	int getP() const{
		return sign(y)==-1||(sign(y)==0&&sign(x)==-1);
	}
	
	inline void read(){
		int a,b;
		cin >> a >> b;
		x=a;y=b;
	}
	inline void display(){
		cerr << "(" << x << "," << y << ") ";
	}
};
 
int inmid(point k1,point k2,point k3){
	return inmid(k1.x,k2.x,k3.x) && inmid(k1.y,k2.y,k3.y);
}
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}

bool left(point k1,point k2,point q){
	return sign(cross(k2-k1,q-k1))>=0;
}
bool on(point k1,point k2,point q){
	return sign(cross(k2-k1,q-k1))==0 && inmid(k1,k2,q);
}
int compareangle(point k1,point k2){
	return k1.getP()<k2.getP()||(k1.getP()==k2.getP()&&sign(cross(k1,k2))>0);
}


typedef long long ll;
const ll mod=998244353;
inline ll ksm(ll a,ll x){
	ll ret=1;
	for (;x;x>>=1,a=a*a % mod) if (x&1) ret=ret*a%mod;
	return ret;
}
inline ll inv(ll a){
	return ksm(a,mod-2);
}

const int maxn=500;
ll n,m;
ll p;
point b[maxn+50];
point a[maxn+50];
bool ok[maxn+50][maxn+50];
ll cost[maxn+50][maxn+50];

int main(){
	ios_base::sync_with_stdio(false);
	cin >> m >> n >> p;
	
	p=p*inv(100) % mod;
	
	for (int i=1;i<=m;i++) b[i].read();
	for (int i=1;i<=n;i++) a[i].read();
	
	sort(a+1,a+n+1,
		[&](const point &A,const point &B){
			return (A.y==B.y)?(A.x<B.x):(A.y<B.y);
		}
	);
	/*
	cerr << "-------------" << endl;
	for (int i=1;i<=n;i++) a[i].display();
	cerr << endl;
	*/
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (i==j) continue;
			bool flag=1;
			for (int k=1;k<=m;k++)
				if (!left(a[i],a[j],b[k])){
					flag=0;
					break;
				}
			if (!flag) continue;
			ok[i][j]=1;
			
			cost[i][j]=1.0;
			if (a[j].y<a[i].y){
				for (int k=1;k<=n;k++){
					if (a[j].y<a[k].y && a[k].y<=a[i].y && left(a[i],a[j],a[k]))
						(cost[i][j]*=inv(mod+1-p))%=mod;
				}
			}
			else if (a[j].y>a[i].y){
				for (int k=1;k<=n;k++){
					if (a[i].y<a[k].y && a[k].y<=a[j].y && !left(a[i],a[j],a[k]))
						(cost[i][j]*=mod+1-p)%=mod;
				}
			}
			else if (a[i].x<a[j].x){
				for (int k=1;k<=n;k++){
					if (on(a[i],a[j],a[k]) && k!=i)
						(cost[i][j]*=inv(mod+1-p))%=mod;
				}
			}
		}
	}
	/*
	cerr << "-----------------" << endl;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cerr << ok[i][j] << " ";
		}
		cerr << endl;
	}
	cerr << endl;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			cerr << cost[i][j] << " ";
		}
		cerr << endl;
	}
	*/
	ll ans=0;
	for (int sel=1;sel<=n;sel++){
		vector<pair<int,int>> List;
		for (int i=sel;i<=n;i++){
			for (int j=sel;j<=n;j++){
				if (i==j) continue;
				if (!ok[i][j]) continue;
				List.emplace_back(i,j);
			}
		}
		sort(List.begin(),List.end(),
			[&](const pair<int,int> &A,const pair<int,int> &B){
				point va=a[A.second]-a[A.first];
				point vb=a[B.second]-a[B.first];
				if (sign(cross(va,vb))==0 && sign(dot(va,vb))>0){
					if (sign(dot(a[A.second]-a[B.second],va))>0) return 1;
					return 0;
				}
				return compareangle(va,vb);
			}
		);
		/*
		cerr << "----------------------" << endl;
		cerr << "point : ";a[sel].display();cerr << endl;
		for (auto [i,j]:List){
			cerr << i << " " << j << endl;
		}
		cerr << "----" << endl;
		*/
		vector<ll> dp(n+5);
		{
			for (auto [i,j]:List){
				ll src=inv(mod+1-p);
				if (i!=sel) src=dp[i];
				dp[j]=(dp[j]+src*cost[i][j]%mod*p)%mod;
				/*
				for (int i=1;i<=n;i++) cerr << dp[i]*16%mod << " ";
				cerr << endl;
				*/
			}
		}
		ll res=dp[sel];
		
	//	cerr << "res : " << res*16%mod << endl;
		res=ksm(mod+1-p,n)*res%mod;
	//	cerr << "res2 : " << res*16%mod << endl;
	
		ans=(ans+res)%mod;
	}
	cout << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 4 50
0 0
-1 0
3 0
0 1
2 -1

output:

686292993

result:

ok single line: '686292993'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

3 5 20
3 0
1 3
5 3
0 0
0 6
6 0
6 6
3 3

output:

771443236

result:

ok single line: '771443236'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

1 2 3
4 5
7 9
-2 -3

output:

184375732

result:

ok single line: '184375732'

Test #4:

score: 0
Accepted
time: 3653ms
memory: 7164kb

input:

500 500 47
7 19
16 17
20 13
1 10
17 9
5 23
12 2
15 12
16 8
11 8
8 12
3 2
11 13
23 0
3 23
13 10
9 12
11 5
8 18
6 0
6 20
3 9
1 21
13 18
5 11
9 15
8 17
6 18
1 8
4 24
7 14
11 11
2 9
8 9
23 3
17 15
21 10
19 7
13 16
0 10
0 7
6 17
11 9
9 4
1 15
21 12
1 24
20 7
21 7
20 0
10 3
3 24
2 12
18 11
20 5
14 20
10 4...

output:

963504722

result:

ok single line: '963504722'

Test #5:

score: -100
Time Limit Exceeded

input:

1 500 55
59773527 -48622950
-76633359 443117719
441925049 713512931
-994603144 -68987280
772876381 722131762
511352639 621437284
-136059566 -211230774
-558357374 -936479782
64380588 -111294401
841774806 594567294
515039746 -199627032
-376709851 386524480
-254296132 210052025
-824608562 909197921
118...

output:


result: