QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#780627 | #8677. Carl’s Vacation | ucup-team5217# | WA | 53ms | 3984kb | C++23 | 3.9kb | 2024-11-25 11:58:52 | 2024-11-25 11:58:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ld= long double;
struct vec{
ld x,y;
vec(ld a=0,ld b=0){x=a,y=b;}
vec operator+(const vec a)const {
return {x+a.x,y+a.y};
}
vec operator-(const vec a)const {
return {x-a.x,y-a.y};
}
vec operator*(ld a)const {
return {x*a,y*a};
}
ld operator*(const vec a)const {
return x*a.x+y*a.y;
}
ld operator^(const vec a)const {
return x*a.y-y*a.x;
}
ld len(){
return sqrt(x*x+y*y);
}
ld len2(){
return (x*x+y*y);
}
};
const ld eps=1e-12;
bool onray(vec a,vec v,vec c){
if(fabs(((c-a)^v))<=eps&&((c-a)*v)>=eps) return true;
return false;
}
int sgn(ld x){
if(x>eps) return 1;
if(fabs(x)<=eps) return 0;
return -1;
}
// ld check(vec a,vec v,vec c,vec d){
// if(on_ray(a,v,c)||on_ray(a,v,d)) return true;
// return sgn(v^(c-a))*sgn(v^(d-a))<0&&sgn((a-d)^(c-d))!=sgn(v^(c-d));
// }
bool online(vec a,vec b,vec c){
if(((c-a)*(c-b))<=-eps&&fabs(((c-a)^(c-b)))<eps) return true;
return false;
}
ld check(vec a,vec b,vec c,vec d){
if(online(a,b,c)||online(a,b,d)||online(c,d,a)||online(c,d,b)) return true;
return sgn((c-b)^(a-b))*sgn((d-b)^(a-b))<-eps&&sgn((a-d)^(c-d))*sgn((b-d)^(c-d))<-eps;
}
ld get_len(vec a,vec v,vec c){
assert(v.len()>=eps);
return ((c-a)^v)/(v.len());
}
struct poly{
ld x1,y1,x2,y2,h;
void read(){
cin>>x1>>y1>>x2>>y2>>h;
}
pair<vec,vec> get(int mo){
if(mo==0) return make_pair(vec(x1,y1),vec(x2,y2));
if(mo==1) return make_pair(vec(x2,y2),vec(x2-(y2-y1),y2+(x2-x1)));
if(mo==2) return make_pair(vec(x2-(y2-y1),y2+(x2-x1)),vec(x1-(y2-y1),y1+(x2-x1)));
if(mo==3) return make_pair(vec(x1-(y2-y1),y1+(x2-x1)),vec(x1,y1));
}
vec getmid(){
return vec(x1+x2,y1+y2)*0.5+vec(-(y2-y1)/2,(x2-x1)/2);
}
};
void solve(void) {
poly a,b;
a.read(),b.read();
ld ans=-1;
for(int i=0;i<4;i++){
pair<vec,vec> p=a.get(i);
for(int j=0;j<4;j++){
pair<vec,vec> q=b.get(j);
ld lo=0,ro=1;
auto get=[&](vec x)->ld {
ld lh=0,rh=1;
auto res=[&](vec y)->ld {
for(int k=0;k<4;k++){
if(k==j) continue;
pair<vec,vec> z=b.get(k);
if(check(x,y,z.first,z.second)) return 1e30;
}
// cerr<<(a.getmid()-x).len2()<<' '<<a.h*a.h<<' '<<(b.getmid()-y).len2()<<' '<<b.h*b.h<<' '<<(x-y).len()<<'\n';
return sqrt((a.getmid()-x).len2()+a.h*a.h)+sqrt((b.getmid()-y).len2()+b.h*b.h)+(x-y).len();
};
while(fabs(lh-rh)>eps){
ld midl=(2*lh+rh)/3;
ld midr=(lh+2*rh)/3;
ld len1=res(q.first+(q.second-q.first)*midl);
ld len2=res(q.first+(q.second-q.first)*midr);
if(len1>=len2) lh=midl;
else rh=midr;
}
return res(q.first+(q.second-q.first)*lh);
};
while(fabs(lo-ro)>eps){
ld midl=(2*lo+ro)/3;
ld midr=(lo+2*ro)/3;
ld len1=get(p.first+(p.second-p.first)*midl);
ld len2=get(p.first+(p.second-p.first)*midr);
if(len1>=len2) lo=midl;
else ro=midr;
}
ld req=get(p.first+(p.second-p.first)*lo);
// cerr<<req<<' '<<i<<' '<<j<<'\n';
if(req!=-1&&(ans==-1||ans>req)) ans=req;
}
}
cout<<setprecision(12)<<ans<<'\n';
return;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int _ = 1;
while (_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 43ms
memory: 3916kb
input:
1 0 0 0 10000 99999 10000 10000 10000 10000
output:
76118.7000492
result:
ok found '76118.7000492', expected '76118.7000492', error '0.0000000'
Test #2:
score: 0
Accepted
time: 34ms
memory: 3860kb
input:
10000 10000 10000 0 10000 0 0 0 10000 10000
output:
32360.679775
result:
ok found '32360.6797750', expected '32360.6797750', error '0.0000000'
Test #3:
score: 0
Accepted
time: 50ms
memory: 3732kb
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: -100
Wrong Answer
time: 53ms
memory: 3984kb
input:
0 0 100 100 20 23 23 18 18 2
output:
126.972542157
result:
wrong answer 1st numbers differ - expected: '88.0567571', found: '126.9725422', error = '0.4419398'