QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179117#7239. TrianglePhantomThreshold#WA 4ms3940kbC++201.1kb2023-09-14 18:14:002023-09-14 18:14:00

Judging History

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

  • [2023-09-14 18:14:00]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3940kb
  • [2023-09-14 18:14:00]
  • 提交

answer

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

const int maxn = 110000;

int n,C;
int a[maxn];

double calc(double x,double y,double z)
{
	double p=(x+y+z)/2;
	return sqrt( p*(p-x)*(p-y)*(p-z) );
}

signed main()
{
	ios_base::sync_with_stdio(false); ////////////////////////////////////////
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>C;
		for(int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+n+1);
		
		double ans=1e15;
		for(int i=2;i<n;i++)
		{
			int l=1,r=i-1;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(a[mid]+a[i]<=a[i+1]) l=mid+1;
				else r=mid-1;
			}r++;
			
			if(r<i) ans=min(ans,calc(a[r],a[i],a[i+1]));
		}
		
		for(int i=1;i<n;i++)
		{
			int k=0;
			for(int j=i+1;j<n;j++)
			{
				if(k<j+1) k=j+1;
				while(k+1<=n && a[i]+a[j]>a[k+1]) k++;
				
				if(a[i]+a[j]>a[k])
				{
					ans=min(ans, calc(a[i],a[j],a[k]));
					break;
				}
			}
		}
		
		if(ans>1e12) cout<<-1<<'\n';
		else cout<<fixed<<setprecision(15)<<ans<<'\n';
	}
	
	return 0;
}

详细

Test #1:

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

input:

4
3 3
1 2 3
4 4
1 2 3 4
3 11
5 7 11
6 11
5 7 8 9 10 11

output:

-1
2.904737509655563
12.968712349342937
12.968712349342937

result:

ok 4 numbers

Test #2:

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

input:

20
5 20
15 20 11 17 18
5 20
12 18 13 20 15
5 20
12 10 14 18 16
5 20
18 16 15 11 14
5 20
18 12 11 20 14
5 20
20 15 10 16 12
5 20
12 10 15 13 17
5 20
18 15 13 20 12
5 20
16 18 20 10 14
5 20
11 15 16 13 18
5 20
11 13 16 14 17
5 20
20 14 11 13 16
5 20
16 11 15 13 18
5 20
11 15 13 20 14
5 20
16 10 13 20 ...

output:

81.259999384691113
74.833147735478832
56.568542494923804
73.484692283495349
56.718052681663885
45.596052460711988
56.995065575889988
74.833147735478832
64.992307237087687
69.628927178292784
67.527772064536535
66.000000000000000
69.628927178292784
66.000000000000000
31.975576617162044
85.451375062078...

result:

ok 20 numbers

Test #3:

score: 0
Accepted
time: 4ms
memory: 3744kb

input:

5000
4 20
11 14 16 17
4 20
13 19 10 15
4 20
19 12 16 14
4 20
11 13 10 15
4 20
17 15 14 18
4 20
14 12 19 15
4 20
13 17 19 11
4 20
16 20 12 18
4 20
20 19 12 16
4 20
14 15 18 17
4 20
16 11 12 15
4 20
10 17 16 19
4 20
17 19 18 13
4 20
11 18 15 20
4 20
19 11 10 16
4 20
18 20 15 11
4 20
17 20 10 15
4 20
1...

output:

75.474747432502213
60.794736614282655
81.332650270355757
53.441556863549550
99.679486355016891
78.926785694084870
69.261731858220230
94.101009558877735
95.503599408608679
99.679486355016891
65.238025721200358
78.226833631433664
105.299572648705464
81.387959797503214
42.426406871192853
81.38795979750...

result:

ok 5000 numbers

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 3940kb

input:

3333
5 30
8 19 7 14 24
5 30
22 29 9 26 21
5 30
27 16 13 10 29
5 30
14 6 25 28 22
5 30
23 19 13 14 21
5 30
24 9 28 30 5
5 30
20 19 23 5 11
5 30
30 7 25 23 11
5 30
22 24 21 15 26
5 30
26 5 28 12 24
5 30
8 23 7 29 14
5 30
29 13 20 24 11
5 30
27 25 13 18 22
5 30
25 27 23 7 18
5 30
16 20 9 12 7
5 30
24 1...

output:

18.799933510520724
50.697016677512693
64.918699155174082
60.555243373303355
81.240384046359608
38.819292883822598
31.275989192989563
66.813172353960269
150.784614599766115
38.819292883822598
18.799933510520724
66.000000000000000
101.034647522520714
49.477267507411923
31.304951684997057
41.2310562561...

result:

wrong answer 27th numbers differ - expected: '31.6533963', found: '47.3286383', error = '0.4952152'