QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796486#21883. Prism Palace (Love Qiwen Xu ver.)skip2004AC ✓41ms8672kbC++201.4kb2024-12-01 19:44:512024-12-01 19:44:53

Judging History

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

  • [2024-12-01 19:44:53]
  • 评测
  • 测评结果:AC
  • 用时:41ms
  • 内存:8672kb
  • [2024-12-01 19:44:51]
  • 提交

answer

//Author: Kevin5307
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
void die(string S){puts(S.c_str());exit(0);}
const long double pi=acosl(-1);
int x[200200],y[200200];
long double angle[200200];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	x[n+1]=x[1];
	y[n+1]=y[1];
	x[0]=x[n];
	y[0]=y[n];
	long double ans=0.0;
	for(int i=1;i<=n;i++)
	{
		int ax=x[i-1]-x[i];
		int ay=y[i-1]-y[i];
		int bx=x[i+1]-x[i];
		int by=y[i+1]-y[i];
		ll prod=(1ll*ax*bx+1ll*ay*by);
		long double lena=sqrtl(1ll*ax*ax+1ll*ay*ay);
		long double lenb=sqrtl(1ll*bx*bx+1ll*by*by);
		long double cosv=prod/lena/lenb;
		angle[i]=acosl(cosv);
	}
	angle[0]=angle[n];
	for(int i=1;i<=n;i++)
		if(angle[i-1]+angle[i]<pi)
			ans+=(pi-angle[i]-angle[i-1]);
	cout<<fixed<<setprecision(15)<<ans/pi<<endl;
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

1.000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

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

input:

4
0 0
0 1
1 1
1 0

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #3:

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

input:

4
0 0
0 3
1 2
1 1

output:

0.500000000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 32ms
memory: 8672kb

input:

199998
-401439104 808964397
-401436126 808965446
-401435185 808965777
-401433632 808966325
-401428358 808968182
-401427134 808968613
-401422823 808970131
-401422094 808970388
-401419626 808971257
-401413017 808973585
-401411225 808974216
-401408435 808975198
-401407425 808975554
-401403924 808976787...

output:

0.000029800320609

result:

ok found '0.0000298', expected '0.0000298', error '0.0000000'

Test #5:

score: 0
Accepted
time: 41ms
memory: 8552kb

input:

199998
761493784 -150716309
761496080 -150712499
761496863 -150711200
761497141 -150710739
761497673 -150709856
761498309 -150708801
761498866 -150707877
761502363 -150702075
761504234 -150698970
761505470 -150696920
761505582 -150696735
761505688 -150696560
761506226 -150695667
761507597 -150693392...

output:

0.000052161573748

result:

ok found '0.0000522', expected '0.0000522', error '0.0000000'

Test #6:

score: 0
Accepted
time: 41ms
memory: 8648kb

input:

199999
-313772198 -315367193
-313768751 -315370633
-313768062 -315371320
-313766641 -315372739
-313766256 -315373122
-313764203 -315375172
-313756449 -315382911
-313750089 -315389258
-313749240 -315390106
-313746581 -315392760
-313745739 -315393600
-313737746 -315401580
-313733885 -315405433
-313730...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

score: 0
Accepted
time: 37ms
memory: 8588kb

input:

199998
-290160652 -194499826
-290161980 -194499251
-290172032 -194494896
-290177477 -194492538
-290183474 -194489940
-290193090 -194485774
-290199951 -194482802
-290205067 -194480585
-290207415 -194479568
-290207541 -194479513
-290217591 -194475159
-290223989 -194472386
-290227374 -194470920
-290233...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

score: 0
Accepted
time: 36ms
memory: 8652kb

input:

200000
82162345 681132396
82161738 681129487
82161553 681128603
82161446 681128088
82160863 681125297
82160735 681124683
82160536 681123729
82159538 681118953
82159394 681118266
82159320 681117910
82159160 681117142
82158780 681115324
82158587 681114399
82158229 681112685
82157954 681111371
82157865...

output:

0.000000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'