QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152389#5443. Security at MuseumsTadijaSebezWA 1ms3788kbC++143.1kb2023-08-28 06:23:192023-08-28 06:23:20

Judging History

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

  • [2023-08-28 06:23:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3788kb
  • [2023-08-28 06:23:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
void ckadd(int&x,int y){x=add(x,y);}
void cksub(int&x,int y){x=sub(x,y);}

struct pt{
	ll x,y;
	pt(){}
	pt(ll a,ll b):x(a),y(b){}
};

pt operator - (const pt& a,const pt& b){
	return pt(a.x-b.x,a.y-b.y);
}
ll cross(const pt& a,const pt& b){
	return a.x*b.y-a.y*b.x;
}
ll dot(const pt& a,const pt& b){
	return a.x*b.x+a.y*b.y;
}

int part(const pt& a){
	if(a.y<0 || (a.y==0 && a.x<0))return 0;
	else return 1;
}

const int N=205;
pt a[N];
bool valid[N][N];

int sgn(ll x){return x==0?0:x<0?-1:1;}

bool intersect(pt A,pt B,pt C,pt D){
	int sa=sgn(cross(D-C,A-C));
	int sb=sgn(cross(D-C,B-C));
	int sc=sgn(cross(B-A,C-A));
	int sd=sgn(cross(B-A,D-A));

	if(sa*sb==1)return false;
	if(sc*sd==1)return false;

	if(sa*sb==-1){
		if(sd*sc==-1)return true;
		if(sd==1){
			if(sc==0){
				ll dotA=dot(B-A,A);
				ll dotB=dot(B-A,B);
				ll dotC=dot(B-A,C);
				if(dotA<=dotC && dotC<=dotB){
					return true;
				}
			}
		}
	}else if(sb==-1){
		if(sa==0){
			return true;
		}
	}
	return false;
}

bool Check(int n,int p,int q){
	auto next=[&](int i){return i==n?1:i+1;};
	for(int f=0;f<2;f++){
		int p1=next(p);
		while(p1!=q && cross(a[p1]-a[p],a[q]-a[p])==0){
			p1=next(p1);
		}
		if(p1==q)return true;
		if(cross(a[p1]-a[p],a[q]-a[p])<0)return false;

		p1=next(p);
		int p0=p;
		while(p1!=q){
			if(p0!=p && intersect(a[p],a[q],a[p0],a[p1])){
				return false;
			}
			p0=p1;
			p1=next(p1);
		}
		swap(p,q);
	}
	return true;
}

struct Event{
	pt dir;
	int i,j;
	Event(pt d,int a,int b):dir(d),i(a),j(b){}
	bool operator < (const Event& other) const {
		int pa=part(dir);
		int pb=part(other.dir);
		if(pa!=pb)return pa<pb;
		ll c=cross(dir,other.dir);
		if(c!=0)return c<0;
		return dot(dir,a[i])<dot(dir,a[other.i]);
	}
};

int dp[N][N];
int main(){
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld %lld",&a[i].x,&a[i].y);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			valid[i][j]=valid[j][i]=Check(n,i,j);
		}
	}
	vector<Event> evs;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(valid[i][j]){
				evs.pb(Event(a[j]-a[i],i,j));
			}
		}
	}
	sort(evs.begin(),evs.end());
	for(int i=1;i<=n;i++){
		dp[i][i]=1;
	}
	for(const Event& ev:evs){
		for(int i=1;i<=n;i++){
			ckadd(dp[i][ev.j],dp[i][ev.i]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ckadd(ans,sub(dp[i][i],1));
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(valid[i][j]){
				int sb=1,ad=1;
				pt dir=a[j]-a[i];
				ll dotA=dot(dir,a[i]);
				ll dotB=dot(dir,a[j]);
				for(int z=1;z<=n;z++){
					if(z!=i && z!=j){
						if(cross(a[i]-a[z],a[j]-a[z])==0){
							ll dotC=dot(dir,a[z]);
							if(dotA<dotC && dotC<dotB){
								sb=mul(sb,4);
								ad=mul(ad,2);
							}
						}
					}
				}
				cksub(ans,sb);
				ckadd(ans,ad);
			}
		}
	}
	printf("%i\n",ans);
	return 0;
}

详细

Test #1:

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

input:

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

output:

56

result:

ok 1 number(s): "56"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

4
0 0
-10 0
-10 -10
0 -10

output:

11

result:

ok 1 number(s): "11"

Test #6:

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

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

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

input:

4
0 0
10 5
20 0
10 10

output:

7

result:

ok 1 number(s): "7"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

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

input:

4
-100 -10
100 -10
100 10
-100 10

output:

11

result:

ok 1 number(s): "11"

Test #10:

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

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

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

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

score: -100
Wrong Answer
time: 1ms
memory: 3700kb

input:

7
0 0
10 10
20 0
30 11
20 22
10 11
0 22

output:

39

result:

wrong answer 1st numbers differ - expected: '44', found: '39'