QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140281 | #4560. 定向越野 | myee | 100 ✓ | 1984ms | 123764kb | C++11 | 7.2kb | 2023-08-15 16:53:05 | 2023-08-15 16:53:07 |
Judging History
answer
// 那就是希望。
// 即便需要取模,也是光明。
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
namespace Geo2D
{
const dbl Pi=acosl(-1);
const dbl eps=1e-9;
struct Dbl
{
dbl v;
Dbl():v(0){}
Dbl(dbl v):v(v){}
dbl&operator()(){return v;}
voi read(){scanf("%lf",&v);}
friend Dbl operator+(Dbl a){return a;}
friend Dbl operator+(Dbl a,Dbl b){return a()+b();}
friend Dbl operator-(Dbl a){return-a();}
friend Dbl operator-(Dbl a,Dbl b){return a()-b();}
friend Dbl operator*(Dbl a,Dbl b){return a()*b();}
friend Dbl operator/(Dbl a,Dbl b){return a()/b();}
friend bol operator<(Dbl a,Dbl b){return a()+eps<b();}
friend bol operator>(Dbl a,Dbl b){return a()>b()+eps;}
friend bol operator<=(Dbl a,Dbl b){return a()<b()+eps;}
friend bol operator>=(Dbl a,Dbl b){return a()+eps>b();}
friend bol operator==(Dbl a,Dbl b){return a()<b()+eps&&a()+eps>b();}
friend bol operator!=(Dbl a,Dbl b){return a()>b()+eps||a()+eps<b();}
Dbl _sin(){return sin(v);}
Dbl _cos(){return cos(v);}
Dbl _acos(){
if(*this==1)return 0;
if(*this==-1)return Pi;
return acos(v);
}
Dbl _sqrt(){return sqrt(v);}
};
struct Vec
{
Dbl x,y;
Vec():x(),y(){}
Vec(Dbl x,Dbl y):x(x),y(y){}
friend Vec operator+(Vec a,Vec b){return{a.x+b.x,a.y+b.y};}
friend Vec operator-(Vec a,Vec b){return{a.x-b.x,a.y-b.y};}
friend Vec operator*(Dbl a,Vec b){return{a*b.x,a*b.y};}
friend Vec operator*(Vec a,Dbl b){return{a.x*b,a.y*b};}
friend Dbl operator*(Vec a,Vec b){return a.x*b.x+a.y*b.y;}
friend Dbl operator^(Vec a,Vec b){return a.x*b.y-a.y*b.x;}
friend Vec operator/(Vec a,Dbl b){return{a.x/b,a.y/b};}
friend bol operator==(Vec a,Vec b){return a.x==b.x&&a.y==b.y;}
Vec&operator+=(Vec b){return*this=*this+b;}
Vec&operator-=(Vec b){return*this=*this-b;}
Dbl len_sqr(){return*this**this;}
Dbl len(){return len_sqr()._sqrt();}
friend Dbl dist_sqr(Vec a,Vec b){return(a-b).len_sqr();}
friend Dbl dist(Vec a,Vec b){return(a-b).len();}
voi read(){x.read(),y.read();}
Vec rotate(Dbl c,Dbl s){return{c*x-s*y,s*x+c*y};}
Vec rotate(Dbl angle){return rotate(angle._cos(),angle._sin());}
int state()
{
if(x>0&&y==0)return 1;
if(x>0&&y>0)return 2;
if(x==0&&y>0)return 3;
if(x<0&&y>0)return 4;
if(x<0&&y==0)return 5;
if(x<0&&y<0)return 6;
if(x==0&&y<0)return 7;
if(x>0&&y<0)return 8;
return 0;
}
};
bol cmp_atan2(Vec a,Vec b){
if(a.state()!=b.state())return a.state()<b.state();
return(a^b)>0;
}
typedef std::vector<Vec>Vecs;
typedef Vec Point;
typedef Vecs Points;
}
// Heaven and Earth... My guiding star...
// Akira Complex R.I.P.
using namespace Geo2D;
Point O[505],P[1000005];Dbl R[505],Dist[1000005];bol G[1000005];uint tp;
std::vector<uint>V[505];std::vector<std::pair<uint,Dbl> >Way[1000005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
freopen("QAQ.out","w",stdout);
#endif
P[0].read(),P[1].read(),tp=2;
uint n=0,m;scanf("%u",&m);while(m--)O[n].read(),R[n].read(),n+=R[n]!=0;
auto check=[&](Point p,Point q)
{
if(p==q)return true;
Vec f=q-p;Vec g=f/f.len_sqr();Dbl r;
for(uint k=0;k<n;k++)if((r=g*(O[k]-p))>0&&r<1&&(p-O[k]+r*f).len()<R[k])return false;
return true;
};
if(check(P[0],P[1]))Way[0].push_back({1,dist(P[0],P[1])}),Way[1].push_back({0,dist(P[0],P[1])});
for(uint o=0;o<2;o++)for(uint i=0;i<n;i++)
{
Dbl d=dist(O[i],P[o]);Dbl c=R[i]/d;Dbl s=(1-c*c)._sqrt();Point p;
p=O[i]+((P[o]-O[i])/d*R[i]).rotate(c,s);
if(check(P[o],p))V[i].push_back(tp),
Way[o].push_back({tp,dist(p,P[o])}),Way[tp].push_back({o,dist(p,P[o])}),P[tp++]=p;
p=O[i]+((P[o]-O[i])/d*R[i]).rotate(c,-s);
if(check(P[o],p))V[i].push_back(tp),
Way[o].push_back({tp,dist(p,P[o])}),Way[tp].push_back({o,dist(p,P[o])}),P[tp++]=p;
}
for(uint i=0;i<n;i++)for(uint j=i+1;j<n;j++)
{
Dbl d=dist(O[i],O[j]),c,s;Point p,q;
c=(R[i]+R[j])/d,s=(1-c*c)._sqrt();
p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(c,s);
if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,-s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(c,-s);
if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
c=(R[i]-R[j])/d,s=(1-c*c)._sqrt();
p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(-c,-s);
if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,-s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(-c,s);
if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
}
for(uint i=0;i<n;i++)
{
std::sort(V[i].begin(),V[i].end(),[&](uint a,uint b){return cmp_atan2(P[a]-O[i],P[b]-O[i]);});
for(uint j=0,a=V[i].back(),b;j<V[i].size();a=b,j++)
{
b=V[i][j];
Dbl d=((P[a]-O[i])*(P[b]-O[i])/(R[i]*R[i]))._acos()*R[i];
Way[a].push_back({b,d}),Way[b].push_back({a,d});
}
}
for(uint i=1;i<tp;i++)Dist[i]=2e5;
std::priority_queue<std::pair<Dbl,uint>,std::vector<std::pair<Dbl,uint> >,std::greater<std::pair<Dbl,uint> > >Q;
Q.push({0,0});
while(Q.size())
{
uint p=Q.top().second;Q.pop();if(G[p])continue;
G[p]=1;for(auto s:Way[p])if(_min(Dist[s.first],Dist[p]+s.second))Q.push({Dist[s.first],s.first});
}
printf("%.1lf\n",Dist[1]());
return 0;
}
// 那就是希望。
// 即便需要取模,也是光明。
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 3ms
memory: 51088kb
input:
-100 27 98 2 0
output:
199.6
result:
ok single line: '199.6'
Test #2:
score: 5
Accepted
time: 5ms
memory: 51400kb
input:
-136 25 171 -3 1 0 0 100
output:
361.1
result:
ok single line: '361.1'
Test #3:
score: 5
Accepted
time: 5ms
memory: 51388kb
input:
-100 0 100 0 1 10 0 10
output:
201.0
result:
ok single line: '201.0'
Test #4:
score: 5
Accepted
time: 3ms
memory: 51228kb
input:
-136 25 174 -4 2 -50 50 60 70 -20 61
output:
340.0
result:
ok single line: '340.0'
Test #5:
score: 5
Accepted
time: 3ms
memory: 51188kb
input:
-136 25 171 -3 2 -50 50 60 80 50 60
output:
314.8
result:
ok single line: '314.8'
Test #6:
score: 5
Accepted
time: 7ms
memory: 51316kb
input:
-136 25 171 -3 3 -50 50 60 10 -20 20 80 50 60
output:
316.5
result:
ok single line: '316.5'
Test #7:
score: 5
Accepted
time: 4ms
memory: 51292kb
input:
-50 90 249 103 4 0 0 100 200 0 100 0 200 100 200 200 100
output:
300.3
result:
ok single line: '300.3'
Test #8:
score: 5
Accepted
time: 6ms
memory: 51584kb
input:
872 -756 -352 288 5 826 775 313 914 429 44 975 357 50 12 920 513 260 -234 667
output:
2203.4
result:
ok single line: '2203.4'
Test #9:
score: 5
Accepted
time: 8ms
memory: 51416kb
input:
-936 602 -345 -983 8 604 180 341 -496 117 166 424 -650 366 531 863 345 -831 133 169 -800 503 167 -127 6 219 -641 -191 174
output:
1775.3
result:
ok single line: '1775.3'
Test #10:
score: 5
Accepted
time: 1ms
memory: 51372kb
input:
-173 -249 -171 -221 16 -225 -309 18 -225 -273 18 -225 -237 18 -225 -201 18 -189 -309 18 -189 -273 18 -189 -237 18 -189 -201 18 -153 -309 18 -153 -273 18 -153 -237 18 -153 -201 18 -117 -309 18 -117 -273 18 -117 -237 18 -117 -201 18
output:
28.2
result:
ok single line: '28.2'
Test #11:
score: 5
Accepted
time: 5ms
memory: 51580kb
input:
985 552 -332 -758 20 329 229 213 926 318 203 -891 -472 129 -41 687 287 -646 692 286 -327 -993 78 -476 -985 71 151 -548 167 -864 -729 129 -406 -59 192 269 -725 27 306 -676 34 -428 -423 37 -32 -835 53 675 -1 202 -61 -961 76 -321 308 184 -350 -438 42 363 -288 89 326 -103 99
output:
1898.6
result:
ok single line: '1898.6'
Test #12:
score: 5
Accepted
time: 6ms
memory: 52164kb
input:
-499 -717 239 -53 50 -817 341 21 21 637 21 398 979 21 -29 -169 21 353 602 21 -758 -744 21 -391 -668 21 217 74 21 -511 54 21 33 15 21 -252 -837 21 -822 863 21 -818 -576 21 978 814 21 934 864 21 -968 -526 21 -998 -79 21 -745 -379 21 491 -161 21 -874 -618 21 -693 -680 21 800 629 21 -140 249 21 223 463 ...
output:
994.2
result:
ok single line: '994.2'
Test #13:
score: 5
Accepted
time: 12ms
memory: 52000kb
input:
-161 -739 -162 -587 100 -251 -761 18 -251 -725 18 -251 -689 18 -251 -653 18 -251 -617 18 -251 -581 18 -251 -545 18 -251 -509 18 -251 -473 18 -251 -437 18 -215 -761 18 -215 -725 18 -215 -689 18 -215 -653 18 -215 -617 18 -215 -581 18 -215 -545 18 -215 -509 18 -215 -473 18 -215 -437 18 -179 -761 18 -17...
output:
152.0
result:
ok single line: '152.0'
Test #14:
score: 5
Accepted
time: 39ms
memory: 52304kb
input:
826 450 -306 925 200 108 673 32 506 283 36 -764 -151 10 830 678 45 -918 -16 98 -25 479 19 299 -70 10 33 787 24 -808 181 35 -446 -32 21 -574 -690 12 835 -921 96 -555 -510 14 -14 515 18 52 -362 7 567 -424 2 -364 -55 48 357 112 84 461 -134 14 340 -717 104 63 -59 7 525 -298 37 289 2 38 -587 167 37 640 -...
output:
1232.9
result:
ok single line: '1232.9'
Test #15:
score: 5
Accepted
time: 154ms
memory: 56980kb
input:
-38 -199 -39 -284 400 -271 -515 18 -271 -479 18 -271 -443 18 -271 -407 18 -271 -371 18 -271 -335 18 -271 -299 18 -271 -263 18 -271 -227 18 -271 -191 18 -271 -155 18 -271 -119 18 -271 -83 18 -271 -47 18 -271 -11 18 -271 25 18 -271 61 18 -271 97 18 -271 133 18 -271 169 18 -235 -515 18 -235 -479 18 -23...
output:
85.1
result:
ok single line: '85.1'
Test #16:
score: 5
Accepted
time: 155ms
memory: 56996kb
input:
166 281 -195 642 400 -281 8 18 -281 44 18 -281 80 18 -281 116 18 -281 152 18 -281 188 18 -281 224 18 -281 260 18 -281 296 18 -281 332 18 -281 368 18 -281 404 18 -281 440 18 -281 476 18 -281 512 18 -281 548 18 -281 584 18 -281 620 18 -281 656 18 -281 692 18 -245 8 18 -245 44 18 -245 80 18 -245 116 18...
output:
574.9
result:
ok single line: '574.9'
Test #17:
score: 5
Accepted
time: 1984ms
memory: 123764kb
input:
776 -462 -166 326 500 -584 400 1 -312 68 1 -235 -138 1 522 100 1 76 701 1 -763 674 1 -873 -149 1 -82 -480 1 560 -945 1 -727 -607 1 -174 619 1 -680 752 1 831 693 1 595 131 1 161 271 1 -984 592 1 70 821 1 -667 -786 1 423 -185 1 148 -769 1 -760 7 1 -872 -388 1 806 -139 1 934 -590 1 668 521 1 22 411 1 1...
output:
1228.1
result:
ok single line: '1228.1'
Test #18:
score: 5
Accepted
time: 1947ms
memory: 122508kb
input:
933 -324 -919 985 500 -357 -466 1 454 150 1 877 -436 1 704 -838 1 -68 -533 1 743 -733 1 466 613 1 -492 -570 1 -675 -456 1 -316 171 1 -558 64 1 -504 517 1 -725 79 1 777 538 1 -622 -808 1 893 6 1 280 225 1 39 -493 1 217 421 1 -405 71 1 -209 888 1 -304 -97 1 -772 740 1 -309 -822 1 487 -558 1 988 214 1 ...
output:
2267.9
result:
ok single line: '2267.9'
Test #19:
score: 5
Accepted
time: 336ms
memory: 53656kb
input:
498 -626 -706 659 500 750 -390 84 -680 797 22 224 -477 45 -276 157 12 825 -215 35 889 365 23 -331 141 41 50 -395 28 710 952 14 857 -605 17 -639 -599 4 645 844 15 -133 963 49 423 434 17 147 631 5 782 359 7 881 782 12 -682 -622 35 -290 347 7 936 -943 5 -986 127 11 301 -17 13 140 957 29 -635 662 42 236...
output:
1785.5
result:
ok single line: '1785.5'
Test #20:
score: 5
Accepted
time: 324ms
memory: 53600kb
input:
622 -445 -234 14 500 618 -568 22 -186 -295 48 777 -658 10 -747 50 20 -731 -783 32 -858 372 10 -395 -690 2 -292 243 7 -590 570 18 -682 550 20 -636 -741 44 901 -668 24 143 196 64 -67 -541 74 607 -986 5 609 -467 24 -670 -684 22 202 -363 28 -827 870 19 440 202 12 -79 209 11 -308 -967 69 374 -42 15 661 4...
output:
974.0
result:
ok single line: '974.0'
Extra Test:
score: 0
Extra Test Passed