QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134561#4942. Robust DefensePhantomThresholdWA 3484ms6724kbC++204.0kb2023-08-03 23:44:222023-08-03 23:44:26

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:44:26]
  • 评测
  • 测评结果:WA
  • 用时:3484ms
  • 内存:6724kb
  • [2023-08-03 23:44:22]
  • 提交

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;
	}
	*/
	vector<pair<int,int>> preList;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (i==j) continue;
			if (!ok[i][j]) continue;
			preList.emplace_back(i,j);
		}
	}
	sort(preList.begin(),preList.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);
		}
	);
	ll ans=0;
	for (int sel=1;sel<=n;sel++){
		vector<ll> dp(n+5);
		for (auto [i,j]:preList){
			if (i>=sel && j>=sel){
				ll src=inv(mod+1-p);
				if (i!=sel) src=dp[i];
				dp[j]=(dp[j]+src*cost[i][j]%mod*p)%mod;
			}
		}
		ll res=dp[sel];
		res=ksm(mod+1-p,n)*res%mod;
	
		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: 5620kb

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: 3620kb

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: 3480kb

input:

1 2 3
4 5
7 9
-2 -3

output:

184375732

result:

ok single line: '184375732'

Test #4:

score: 0
Accepted
time: 1743ms
memory: 6612kb

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: 0
Accepted
time: 3163ms
memory: 6724kb

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:

185827470

result:

ok single line: '185827470'

Test #6:

score: -100
Wrong Answer
time: 3484ms
memory: 6608kb

input:

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

output:

36085402

result:

wrong answer 1st lines differ - expected: '682068131', found: '36085402'