QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#179120 | #7239. Triangle | PhantomThreshold# | WA | 4ms | 3888kb | C++20 | 1.1kb | 2023-09-14 18:15:39 | 2023-09-14 18:15:39 |
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];
long double calc(long double x,long double y,long double z)
{
long double p=(x+y+z)/2;
return sqrtl( 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);
long 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
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: 3824kb
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.833147735478828 56.568542494923802 73.484692283495343 56.718052681663887 45.596052460711991 56.995065575889989 74.833147735478828 64.992307237087683 69.628927178292787 67.527772064536529 66.000000000000000 69.628927178292787 66.000000000000000 31.975576617162043 85.451375062078...
result:
ok 20 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 3884kb
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.474747432502217 60.794736614282655 81.332650270355755 53.441556863549550 99.679486355016898 78.926785694084869 69.261731858220236 94.101009558877741 95.503599408608679 99.679486355016898 65.238025721200362 78.226833631433658 105.299572648705465 81.387959797503218 42.426406871192851 81.38795979750...
result:
ok 5000 numbers
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 3788kb
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.799933510520722 50.697016677512692 64.918699155174081 60.555243373303356 81.240384046359604 38.819292883822601 31.275989192989564 66.813172353960263 150.784614599766113 38.819292883822601 18.799933510520722 66.000000000000000 101.034647522520709 49.477267507411927 31.304951684997056 41.2310562561...
result:
wrong answer 27th numbers differ - expected: '31.6533963', found: '47.3286383', error = '0.4952152'