QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179117 | #7239. Triangle | PhantomThreshold# | WA | 4ms | 3940kb | C++20 | 1.1kb | 2023-09-14 18:14:00 | 2023-09-14 18:14:00 |
Judging History
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'