QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786646 | #8677. Carl’s Vacation | Wolam | WA | 1ms | 3924kb | C++20 | 3.9kb | 2024-11-26 22:38:21 | 2024-11-26 22:38:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double __float128
const double eps=1e-12;
struct ss{
double x,y;
double len()
{
return sqrtl(x*x+y*y);
}
double operator *(const ss ot)const{
return x*ot.x+y*ot.y;
}
ss operator -(const ss ot)const{
return (ss){x-ot.x,y-ot.y};
}
ss operator +(const ss ot)const{
return (ss){x+ot.x,y+ot.y};
}
ss operator *(const double ot)const{
return (ss){x*ot,y*ot};
}
}a[4],b[4];
double mul(ss A,ss B)
{
return A.x*B.y-A.y*B.x;
}
bool check(ss A,ss B,ss C,ss D)
{
double l=min(A.x,B.x),r=max(A.x,B.x);
double L=min(C.x,D.x),R=max(C.x,D.x);
if(r+eps<L||R+eps<l)return 0;
l=min(A.y,B.y),r=max(A.y,B.y);
L=min(C.y,D.y),R=max(C.y,D.y);
if(r+eps<L||R+eps<l)return 0;
if(mul(B-A,C-A)*mul(B-A,D-A)>eps)
return 0;
if(mul(D-C,A-C)*mul(D-C,B-C)>eps)
return 0;
return 1;
}
void sol()
{
int x1,y1,x2,y2,h1,h2;
cin>>x1>>y1>>x2>>y2>>h1;
a[0]=(ss){x1,y1};
a[1]=(ss){x2,y2};
ss p=a[1]-a[0];
a[2]=(ss){a[1].x-p.y,a[1].y+p.x};
a[3]=(ss){a[2].x-p.x,a[2].y-p.y};
cin>>x1>>y1>>x2>>y2>>h2;
b[0]=(ss){x1,y1};
b[1]=(ss){x2,y2};
p=b[1]-b[0];
b[2]=(ss){b[1].x-p.y,b[1].y+p.x};
b[3]=(ss){b[2].x-p.x,b[2].y-p.y};
//cout<<(float)b[3].x<<" "<<(float)b[3].y<<endl;
ss m1=(ss){(a[0].x+a[2].x)/2,(a[0].y+a[2].y)/2};
ss m2=(ss){(b[0].x+b[2].x)/2,(b[0].y+b[2].y)/2};
double d1=mul(m1-a[0],a[1]-a[0])/(a[1]-a[0]).len();
double d2=mul(m2-b[0],b[1]-b[0])/(b[1]-b[0]).len();
double len1=sqrtl(h1*h1+d1*d1);
double llen1=sqrtl(h1*h1+(m1-a[0]).len()*(m1-a[0]).len());
//cerr<<len1<<'\n';
double len2=sqrtl(h2*h2+d2*d2);
double llen2=sqrtl(h2*h2+(m2-b[0]).len()*(m2-b[0]).len());
//cerr<<(float)len2<<'\n';
double ans=1e18;
for(int i=0;i<4;i++)
{
ss mm1=(ss){(a[i].x+a[(i+1)%4].x)/2,(a[i].y+a[(i+1)%4].y)/2};
ss p1=m1-mm1;
ss E=mm1+p1*(len1/p1.len());
//cerr<<(float)len1<<" "<<(float)p1.len()<<endl;
for(int j=0;j<4;j++)
{
ss mm2=(ss){(b[j].x+b[(j+1)%4].x)/2,(b[j].y+b[(j+1)%4].y)/2};
ss p2=m2-mm2;
ss F=mm2+p2*(len2/p2.len());
//cout<<(float)E.x<<" "<<(float)E.y<<" "<<(float)F.x<<" "<<(float)F.y<<" "<<(float)b[j].x<<" "<<(float)b[j].y<<" "<<(float)b[(j+1)%4].x<<" "<<(float)b[(j+1)%4].y<<endl;
if(check(b[j],b[(j+1)%4],E,F)&&check(a[i],a[(i+1)%4],E,F))
{
//cout<<(float)E.x<<" "<<(float)E.y<<" "<<(float)F.x<<" "<<(float)F.y<<" "<<i<<" "<<j<<" "<<(float)b[2].x<<" "<<(float)b[2].y<<endl;
ans=min(ans,(E-F).len());
}
if(check(b[j],b[(j+1)%4],a[i],F))
{
ans=min(ans,(a[i]-F).len()+llen1);
}
if(check(a[i],a[(i+1)%4],b[j],E))
{
ans=min(ans,(b[j]-E).len()+llen2);
}
ans=min(ans,(a[i]-b[j]).len()+llen1+llen2);
}
}
#undef double
cout<<fixed<<setprecision(9)<<(long double)ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
sol();
}
/*
0 0 10 0 4
9 18 34 26 42
5 3.31662 21.5 67.5391 9 26 34 26 1
5 3.31662 21.5 67.5391 9 26 34 26 1
5 3.31662 21.5 67.5391 9 26 34 26 1
5 3.31662 21.5 67.5391 9 26 34 26 1
6.68338 5 -7.53914 38.5 34 26 34 51 0
6.68338 5 -7.53914 38.5 34 26 34 51 0
6.68338 5 -7.53914 38.5 34 26 34 51 0
6.68338 5 -7.53914 38.5 34 26 34 51 0
5 6.68338 21.5 9.46086 34 51 9 51 0
5 6.68338 21.5 9.46086 34 51 9 51 0
5 6.68338 21.5 9.46086 34 51 9 51 0
5 6.68338 21.5 9.46086 34 51 9 51 0
3.31662 5 50.5391 38.5 9 51 9 26 0
3.31662 5 50.5391 38.5 9 51 9 26 0
3.31662 5 50.5391 38.5 9 51 9 26 0
3.31662 5 50.5391 38.5 9 51 9 26 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
1 0 0 0 10000 99999 10000 10000 10000 10000
output:
76118.700049220
result:
ok found '76118.7000492', expected '76118.7000492', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
10000 10000 10000 0 10000 0 0 0 10000 10000
output:
32360.679774998
result:
ok found '32360.6797750', expected '32360.6797750', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
0 0 100 100 20 0 0 -5 -5 2
output:
107.365555079
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
0 0 100 100 20 23 23 18 18 2
output:
88.056757051
result:
ok found '88.0567571', expected '88.0567571', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
0 0 100 100 20 100 100 105 95 2
output:
107.365555079
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
0 0 100 100 20 44 156 49 151 2
output:
77.704520218
result:
ok found '77.7045202', expected '77.7045202', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
0 0 100 100 20 200 0 205 5 2
output:
224.528035157
result:
ok found '224.5280352', expected '224.5280352', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
0 0 100 100 20 -29 171 -24 176 2
output:
84.368195798
result:
ok found '84.3681958', expected '84.3681958', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
0 0 100 100 20 -100 100 -105 105 2
output:
107.365555079
result:
ok found '107.3655551', expected '107.3655551', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
0 0 100 100 20 -69 69 -74 74 2
output:
83.294612444
result:
ok found '83.2946124', expected '83.2946124', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
0 0 30 0 20 50 20 80 20 20
output:
72.801098893
result:
ok found '72.8010989', expected '72.8010989', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
0 0 30 0 20 50 20 80 20 140
output:
186.874948276
result:
ok found '186.8749483', expected '186.8749483', error '0.0000000'
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 3868kb
input:
0 0 30 0 140 50 20 80 20 140
output:
202.592178800
result:
wrong answer 1st numbers differ - expected: '302.2649538', found: '202.5921788', error = '0.3297530'