QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558628#5443. Security at Museumsucup-team052WA 0ms3832kbC++233.8kb2024-09-11 17:12:502024-09-11 17:12:51

Judging History

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

  • [2024-09-11 17:12:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-09-11 17:12:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y) {return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y) {return 1ULL*x*y%mod;}
using db=long double;
const db eps=1e-9;
int sgn(db x)
{
	if(x<-eps) return -1;
	else if(x>eps) return 1;
	else return 0;
}
struct Vec{
	db x,y;
	Vec(db a=0,db b=0) {x=a,y=b;}
	db norm() {return x*x+y*y;}
	db abs() {return sqrt(x*x+y*y);}
	db arg() const { return atan2(y, x); }
};
Vec operator + (Vec x,Vec y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (Vec x,Vec y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (Vec x,db y) {return Vec(x.x*y,x.y*y);}
Vec operator / (Vec x,db y) {return Vec(x.x/y,x.y/y);}
db cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
db cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int ccw(const Vec &x,const Vec &y,const Vec &z) {return sgn(cross(y-x,z-x));}
int half(Vec v) {return v.y<0||(v.y==0&&v.x<0);}
int cmp(Vec x,Vec y){
	return half(x)==half(y)?cross(x,y)>0:half(y);
}
struct Seg
{
	Vec s,t;
	Seg() {}
	Seg(Vec p,Vec q) {s=p,t=q;}
	int onseg(Vec o)
	{
		return sgn(cdot(o-s,o-t))<=0&&sgn(cross(o-s,o-t))==0;
	}
};
int intersect(Seg p,Seg q) // strict intersect
{
	return ccw(p.s,p.t,q.s)*ccw(p.s,p.t,q.t)==-1&&ccw(q.s,q.t,p.s)*ccw(q.s,q.t,p.t)==-1;
}
Vec crosspoint(Seg p,Seg q)
{
	db A=cross(p.t-p.s,q.t-q.s);
	db B=cross(p.t-p.s,p.t-q.s);
	return q.s+(q.t-q.s)*(B/A);
}
bool seginpolygon(const vector<Vec> &a,int i,int j){
	auto chkin=[&](Vec O,Vec P,Vec Q,Vec R)
	{
		if(ccw(O,P,Q)==1) return ccw(O,P,R)>=0&&ccw(O,R,Q)>=0;
		else return !(ccw(O,Q,R)==1&&ccw(O,R,P)==1);
	};
	int n=a.size();
	if(!chkin(a[i],a[(i+1)%n],a[(i-1+n)%n],a[j])) return 0;
	if(!chkin(a[j],a[(j+1)%n],a[(j-1+n)%n],a[i])) return 0;
	int ok=1; Seg cur(a[i],a[j]);
	for(int k=0;k<n;k++) if(intersect(cur,Seg(a[k],a[(k+1)%n]))) ok=0;
	if(!ok) return 0;
	for(int k=0;k<n;k++)
	{
		if(k==i||k==j) continue;
		if(cur.onseg(a[k]))
		{
			if(!chkin(a[k],a[(k+1)%n],a[(k-1+n)%n],a[i])) ok=0;
			if(!chkin(a[k],a[(k+1)%n],a[(k-1+n)%n],a[j])) ok=0;
		}
	}
	return ok;
}
#define N 205
Vec a[N];
vector<Vec> all;
int n;
struct Edge{
	int i,j;
	Vec get() {return a[j]-a[i];}
};
bool cmpseg(Edge x,Edge y){
	Vec A=x.get(),B=y.get();
	if(!cmp(A,B)&&!cmp(B,A)) return cdot(a[x.i],A)<cdot(a[y.i],A);
	else return cmp(A,B);
}
vector<Edge> edges;
int ans;
int f[N],pw4[N],pw2[N];
signed main()
{
#ifdef xay5421
	freopen("b.in","r",stdin);
#endif
	pw4[0]=1; for(int i=1;i<N;i++) pw4[i]=mul(pw4[i-1],4);
	pw2[0]=1; for(int i=1;i<N;i++) pw2[i]=mul(pw2[i-1],2);
	cin>>n; for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
	all=vector<Vec>(a,a+n);
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j)
	{
		if(seginpolygon(all,i,j)) edges.push_back({i,j});
	}
	sort(edges.begin(),edges.end(),cmpseg);
	// for(auto [x,y]:edges) printf("%d %d\n",x,y);
	for(int i=0;i<n;i++)
	{
		memset(f,0,sizeof(f));
		f[i]=1;
		for(auto [x,y]:edges)
		{
			f[y]=add(f[y],f[x]);
		}
		ans=add(ans,f[i]);
		// cout<<i<<" "<<f[i]<<endl;
	}
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
	{
		Seg s(a[i],a[j]);
		int cnt=0;
		for(int k=0;k<n;k++) if(k!=i&&k!=j) cnt+=s.onseg(a[k]);
		ans=sub(ans,pw4[cnt]);
		ans=add(ans,pw2[cnt]);
	}
	cout<<sub(ans,n)<<endl;
	return 0;
}




Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3832kb

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

input:

3
0 2022
-2022 -2022
2022 0

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

3
4 0
0 3
0 0

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

3
-10 0
10 0
0 18

output:

4

result:

ok 1 number(s): "4"

Test #5:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #6:

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

input:

4
-100 0
0 -100
100 0
0 100

output:

11

result:

ok 1 number(s): "11"

Test #7:

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

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

input:

4
0 0
20 0
30 10
10 10

output:

11

result:

ok 1 number(s): "11"

Test #9:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #10:

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

input:

4
0 0
100 0
60 30
0 30

output:

11

result:

ok 1 number(s): "11"

Test #11:

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

input:

4
0 0
100 0
60 30
40 30

output:

11

result:

ok 1 number(s): "11"

Test #12:

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

input:

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

output:

44

result:

ok 1 number(s): "44"

Test #13:

score: -100
Wrong Answer
time: 0ms
memory: 3808kb

input:

10
0 0
10 10
20 0
30 10
40 0
40 21
30 11
20 21
10 11
0 21

output:

89

result:

wrong answer 1st numbers differ - expected: '93', found: '89'