QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357020 | #5104. Guardians of the Gallery | TadijaSebez | WA | 1696ms | 4172kb | C++14 | 7.0kb | 2024-03-18 17:32:12 | 2024-03-18 17:32:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define pb push_back
#define ldb double
ll gcd(ll a,ll b){
return a==0?b:gcd(b%a,a);
}
ll myabs(ll a){return a<0?-a:a;}
struct frac{
ll p,q;
frac():p(0),q(1){}
frac(ll x):p(x),q(1){}
frac(ll a,ll b){
if(b<0)b=-b,a=-a;
ll g=gcd(myabs(a),b);
p=a/g;
q=b/g;
}
ldb to_ldb(){
return (ldb)p/q;
}
void Print(){
printf("%lf",to_ldb());
}
};
frac operator + (frac a,frac b){
return frac(a.p*b.q+b.p*a.q,a.q*b.q);
}
frac operator - (frac a,frac b){
return frac(a.p*b.q-b.p*a.q,a.q*b.q);
}
frac operator - (frac a){
return frac(-a.p,a.q);
}
frac operator * (frac a,frac b){
return frac(a.p*b.p,a.q*b.q);
}
frac operator * (frac a,ll b){
return frac(a.p*b,a.q);
}
frac operator / (frac a,frac b){
return frac(a.p*b.q,a.q*b.p);
}
frac operator / (frac a,ll b){
return frac(a.p,a.q*b);
}
bool operator < (frac a,frac b){
return a.p*b.q < b.p*a.q;
}
bool operator < (frac a,ll b){
return a.p < b*a.q;
}
bool operator == (frac a,frac b){
return a.p*b.q == b.p*a.q;
}
bool operator == (frac a,ll b){
return a.p == b*a.q;
}
bool operator <= (frac a,frac b){
return a<b || a==b;
}
bool operator <= (frac a,ll b){
return a<b || a==b;
}
int sgn(frac x){
if(x<0)return -1;
if(x==0)return 0;
return 1;
}
struct pt{
frac x,y;
pt():x(0),y(0){}
pt(ll a,ll b):x(a),y(b){}
pt(frac a,frac b):x(a),y(b){}
void Print(){
printf("(");
x.Print();
printf(", ");
y.Print();
printf(") ");
}
};
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator - (pt a){return pt(-a.x,-a.y);}
pt operator * (pt a,ll b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ll b){return pt(a.x/b,a.y/b);}
pt operator * (pt a,frac b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,frac b){return pt(a.x/b,a.y/b);}
frac cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
frac dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ldb dist(pt a,pt b){
ldb x1=a.x.to_ldb();
ldb y1=a.y.to_ldb();
ldb x2=b.x.to_ldb();
ldb y2=b.y.to_ldb();
ldb dx=x1-x2;
ldb dy=y1-y2;
return sqrt(dx*dx+dy*dy);
}
pt perp(pt a){return pt(-a.y,a.x);}
struct line{
pt from,to;
pt v;
frac c;
line(pt a,pt b){
from=a;
to=b;
v=b-a;
c=cross(v,a);
}
line(pt a,pt b,pt dir){
from=a;
to=b;
v=dir;
c=cross(v,a);
}
frac side(pt p){
return -cross(v,p)+c;
}
frac offs(pt p){
return dot(v,p);
}
bool onRay(pt p){
return offs(from)<offs(p);
}
bool onSegment(pt p){
return offs(from)<=offs(p) && offs(p)<=offs(to);
}
};
pt inter(line a,line b){
return (b.v*a.c-a.v*b.c)/cross(a.v,b.v);
}
bool parallel(line a,line b){
return cross(a.v,b.v)==0;
}
vector<pt> poly;
int n;
vector<line> cand;
line GetCand(pt from,pt to){
line a=line(from,to);
bool hasL=false,hasR=false;
pt L,R;
for(int i=0;i<n;i++){
int j=(i+1)%n;
int s1=sgn(a.side(poly[i]));
int s2=sgn(a.side(poly[j]));
if(s1!=0 && s2!=0){
if(s1!=s2){
pt p=inter(a,line(poly[i],poly[j]));
/*if(!(a.side(p)==0)){
a.from.Print();
a.to.Print();
printf(" x ");
poly[i].Print();
poly[j].Print();
printf(" => ");
p.Print();
printf("\n");
}
assert(a.side(p)==0);*/
if(a.onRay(p)){
if(!hasL || a.offs(p)<a.offs(L)){
L=p;hasL=true;
}
if(!hasR || a.offs(p)<a.offs(R)){
R=p;hasR=true;
}
}
}
}else if(s1==0 && s2==0){
}else{
pt p;
if(s1==0){
p=poly[i];
}else{
p=poly[j];
}
int s3=s1+s2;
if(a.onRay(p)){
if(s3==-1){
if(!hasL || a.offs(p)<a.offs(L)){
L=p;hasL=true;
}
}else{
if(!hasR || a.offs(p)<a.offs(R)){
R=p;hasR=true;
}
}
}
}
}
//printf("GetCand ");
//from.Print();
//to.Print();
//printf("%i %i\n",hasL,hasR);
//L.Print();
//R.Print();
//printf("\n");
if(!hasL && !hasR)return line(from,from);
if(!hasL)return line(from,R,to-from);
if(!hasR)return line(from,L,to-from);
if(a.offs(L)<a.offs(R)){
return line(from,R,to-from);
}else{
return line(from,L,to-from);
}
}
bool Inside(pt p){
int cnt=0;
for(int i=0;i<n;i++){
int j=(i+1)%n;
line seg=line(poly[i],poly[j]);
if(seg.side(p)==0 && seg.onSegment(p))return true;
cnt+=((p.y<poly[i].y)-(p.y<poly[j].y))*sgn(cross(poly[i]-p,poly[j]-p))>0;
}
return cnt%2==1;
}
pt S,E;
const int N=105;
const ldb inf=1e18;
ldb dp[N];
bool was[N];
vector<pair<int,ldb>> G[N];
int main(){
scanf("%i",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%i %i",&x,&y);
poly.pb(pt(x,y));
}
int sx,sy,ex,ey;
scanf("%i %i",&sx,&sy);
S=pt(sx,sy);
scanf("%i %i",&ex,&ey);
E=pt(ex,ey);
for(pt p:poly){
cand.pb(GetCand(E,p));
//cand.back().from.Print();
//cand.back().to.Print();
//printf("\n");
}
cand.pb(GetCand(E,S));
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
line seg=GetCand(poly[i],poly[j]);
ldb d=dist(poly[i],poly[j]);
//printf("Ray %i - %i: ",i+1,j+1);
//seg.to.Print();
//printf("\n");
if(seg.onSegment(poly[j]) && Inside((poly[i]+poly[j])/2)){
G[i].pb({j,d});
G[j].pb({i,d});
//printf("Edge\n");
}
}
}
for(int i=0;i<n;i++){
line seg=GetCand(S,poly[i]);
ldb d=dist(S,poly[i]);
//printf("Ray S - %i: ",i+1);
//seg.to.Print();
//printf("\n");
if(seg.onSegment(poly[i])){
G[n].pb({i,d});
//printf("Edge\n");
}
}
for(int i=0;i<n;i++)dp[i]=inf;
dp[n]=0;
while(true){
ldb now=inf;
int best=-1;
for(int j=0;j<=n;j++){
if(!was[j] && dp[j]<now){
now=dp[j];
best=j;
}
}
if(best==-1)break;
was[best]=true;
for(auto e:G[best]){
dp[e.first]=min(dp[e.first],dp[best]+e.second);
}
}
ldb ans=inf;
for(int i=0;i<=n;i++){
if(was[i]){
pt p=i==n?S:poly[i];
//if(i<n)printf("Try %i\n",i+1);
//else printf("Try S\n");
for(int j=0;j<cand.size();j++){
line seg=cand[j];
if(seg.v.x==0 && seg.v.y==0)continue;
//printf("Seg %i\n",j);
//seg.to.Print();
//printf("\n");
int s=sgn(seg.side(p));
//printf("%i\n",s);
if(s==0){
if(seg.onSegment(p)){
ans=min(ans,dp[i]);
//printf("ANS %.12lf\n",dp[i]);
}
}else{
pt dir=perp(seg.v);
if(s==-1)dir=-dir;
//printf("Dir ");
//seg.v.Print();
//dir.Print();
//printf("\n");
//printf("===================================\n");
line ray=GetCand(p,p+dir);
//printf("Perp ray ");
//ray.from.Print();
//ray.to.Print();
//printf("\n");
if(!parallel(ray,seg)){
pt o=inter(ray,seg);
if(seg.onSegment(o) && ray.onSegment(o)){
ans=min(ans,dp[i]+dist(p,o));
//printf("ANS %.12lf\n",dp[i]+dist(p,o));
}
}
ray=GetCand(p,seg.to);
if(ray.onSegment(seg.to) && Inside((p+seg.to)/2)){
ans=min(ans,dp[i]+dist(p,seg.to));
}
}
}
}
}
printf("%.12lf\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 3808kb
input:
15 13 7 20 20 39 20 49 7 73 13 100 5 117 38 98 20 80 20 66 40 68 20 51 20 41 39 22 48 2 39 10 20 104 20
output:
29.000000000000
result:
ok found '29.0000000', expected '29.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 7ms
memory: 3788kb
input:
16 39 2 48 22 39 41 20 51 20 68 40 66 20 80 20 98 38 117 5 100 13 73 7 49 19 39 20 23 20 20 7 13 20 10 20 104
output:
13.000000000000
result:
ok found '13.0000000', expected '13.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 6ms
memory: 3920kb
input:
16 13 33 20 60 23 66 39 97 49 105 73 166 100 205 117 272 98 216 80 180 66 172 68 156 51 122 41 121 22 92 2 44 10 40 104 228
output:
140.872282582487
result:
ok found '140.8722826', expected '140.8722826', error '0.0000000'
Test #4:
score: 0
Accepted
time: 9ms
memory: 3932kb
input:
16 64 17 50 28 67 23 65 18 77 4 88 20 78 10 70 29 61 28 47 32 54 17 43 13 35 20 41 30 27 20 42 6 81 12 33 23
output:
64.204537702523
result:
ok found '64.2045377', expected '64.2045377', error '0.0000000'
Test #5:
score: 0
Accepted
time: 8ms
memory: 3924kb
input:
16 64 17 50 28 67 23 65 18 77 4 88 20 78 10 70 29 61 28 47 32 54 17 43 13 35 20 41 30 27 20 42 6 33 23 81 12
output:
72.283498041177
result:
ok found '72.2834980', expected '72.2834980', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
7 76 8 389 215 691 19 407 331 489 397 300 403 363 334 126 60 393 370
output:
6.657917756511
result:
ok found '6.6579178', expected '6.6579178', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
3 0 1000 1000 0 1000 1000 567 578 589 601
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
3 0 1000 0 0 1000 0 366 366 367 366
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
5 50 93 278 178 199 300 596 362 208 519 421 388 142 153
output:
175.169759391735
result:
ok found '175.1697594', expected '175.1697594', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3808kb
input:
7 50 93 278 178 199 300 401 312 483 162 596 362 208 519 488 252 142 153
output:
289.682139876890
result:
ok found '289.6821399', expected '289.6821399', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 4100kb
input:
8 10 10 40 25 20 25 20 35 12 23 30 23 10 20 5 40 15 15 19 26
output:
25.000000000000
result:
ok found '25.0000000', expected '25.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
9 5 1000 6 3 5 999 0 1000 0 0 500 2 500 0 1000 0 1000 1000 1 4 993 1
output:
5.101047906986
result:
ok found '5.1010479', expected '5.1010479', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1696ms
memory: 3972kb
input:
100 695 43 538 87 463 208 597 329 750 306 812 481 960 555 912 344 983 450 987 573 994 852 941 985 801 855 792 800 849 806 792 696 924 701 939 672 710 546 722 668 723 807 715 767 624 524 634 554 547 503 357 352 627 458 651 495 937 558 932 545 864 509 753 489 509 397 341 335 300 495 199 528 380 688 48...
output:
1695.186573023642
result:
ok found '1695.1865730', expected '1695.1865730', error '0.0000000'
Test #14:
score: 0
Accepted
time: 23ms
memory: 4172kb
input:
20 840 854 839 45 996 905 959 938 852 938 730 423 425 493 136 481 213 778 527 740 691 941 22 830 83 313 462 155 636 21 462 321 360 324 238 422 402 492 806 406 952 822 410 838
output:
1424.384201454849
result:
ok found '1424.3842015', expected '1424.3842015', error '0.0000000'
Test #15:
score: 0
Accepted
time: 688ms
memory: 4092kb
input:
74 89 395 52 622 124 832 115 698 95 598 199 491 190 356 191 398 132 315 94 371 34 221 91 0 153 139 220 465 260 283 312 30 409 15 338 50 343 52 437 69 359 89 332 213 377 505 375 396 405 199 657 90 658 50 360 50 618 23 642 7 824 191 688 417 795 227 709 286 662 321 646 175 485 210 381 357 420 329 441 3...
output:
2036.755709876637
result:
ok found '2036.7557099', expected '2036.7557099', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1566ms
memory: 4028kb
input:
100 380 626 511 639 548 551 651 476 706 462 636 604 652 617 776 577 794 566 821 433 765 410 778 276 735 345 700 329 448 550 283 482 537 332 706 213 741 204 833 152 657 182 626 173 568 225 602 213 673 203 537 286 459 317 609 261 493 344 334 430 468 338 331 400 350 326 512 197 553 155 424 120 446 179 ...
output:
307.850710857283
result:
ok found '307.8507109', expected '307.8507109', error '0.0000000'
Test #17:
score: 0
Accepted
time: 1645ms
memory: 4028kb
input:
100 425 641 614 667 719 714 598 761 548 727 505 713 415 832 505 856 724 762 764 767 803 755 773 727 826 633 832 509 842 570 829 456 742 430 706 513 604 527 942 208 912 569 959 330 975 605 977 878 882 609 844 694 869 789 930 896 992 894 763 937 699 930 701 854 732 810 709 820 657 881 507 896 342 805 ...
output:
1941.568735726889
result:
ok found '1941.5687357', expected '1941.5687357', error '0.0000000'
Test #18:
score: 0
Accepted
time: 1606ms
memory: 4120kb
input:
100 845 528 842 889 837 997 809 663 786 746 793 554 782 470 769 798 709 992 520 993 95 983 191 897 250 666 136 715 139 745 32 979 32 918 5 916 0 740 31 283 10 238 36 177 102 740 141 635 145 353 132 435 106 607 130 383 41 66 139 12 403 11 330 45 225 48 153 216 251 342 233 374 289 424 266 99 334 62 34...
output:
1863.571740263406
result:
ok found '1863.5717403', expected '1863.5717403', error '0.0000000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
4 0 0 1000 0 1000 1000 0 1000 4 939 27 58
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #20:
score: 0
Accepted
time: 1019ms
memory: 4076kb
input:
94 5 5 995 5 995 995 5 995 990 990 5 990 970 970 5 970 950 950 5 950 930 930 5 930 910 910 5 910 890 890 5 890 870 870 5 870 850 850 5 850 830 830 5 830 810 810 5 810 790 790 5 790 770 770 5 770 750 750 5 750 730 730 5 730 710 710 5 710 690 690 5 690 670 670 5 670 650 650 5 650 630 630 5 630 610 610...
output:
620.291060712630
result:
ok found '620.2910607', expected '620.2910607', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
8 0 0 20 0 20 30 60 30 60 0 80 0 80 50 0 50 70 30 70 10
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
5 2 0 10 0 0 10 0 3 5 3 1 8 5 2
output:
5.000000000000
result:
ok found '5.0000000', expected '5.0000000', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
5 2 0 10 0 0 10 0 3 5 3 1 4 5 2
output:
4.000000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3976kb
input:
12 0 0 2 0 2 4 1 4 1 5 2 5 2 7 0 7 0 3 1 3 1 2 0 2 1 6 1 1
output:
2.000000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
10 0 0 2 0 2 4 1 4 2 5 2 7 0 7 0 3 1 2 0 2 1 6 1 1
output:
2.000000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #26:
score: 0
Accepted
time: 3ms
memory: 3912kb
input:
12 0 0 2 0 3 3 5 0 6 3 7 0 8 2 7 6 5 2 4 6 2 2 0 2 1 1 7 1
output:
6.478708664619
result:
ok found '6.4787087', expected '6.4787087', error '0.0000000'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
8 10 0 11 3 12 0 14 0 15 3 16 0 18 4 8 4 10 1 16 1
output:
5.876122922140
result:
ok found '5.8761229', expected '5.8761229', error '0.0000000'
Test #28:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
8 10 0 11 3 12 0 16 3 14 0 17 0 17 4 8 4 10 1 15 1
output:
7.236067977500
result:
ok found '7.2360680', expected '7.2360680', error '0.0000000'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
8 0 0 20 0 20 30 60 30 60 0 80 0 80 50 0 50 70 10 10 10
output:
58.137767414995
result:
ok found '58.1377674', expected '58.1377674', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
11 0 0 4 0 4 1 5 1 5 0 7 0 7 2 3 2 3 1 2 2 0 2 6 1 1 1
output:
2.000000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #31:
score: 0
Accepted
time: 1ms
memory: 4164kb
input:
3 31 41 59 26 53 58 36 41 56 31
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #32:
score: -100
Wrong Answer
time: 710ms
memory: 3816kb
input:
97 6 10 8 10 8 12 6 12 6 14 4 8 2 6 2 10 4 10 2 12 4 12 4 14 0 14 0 0 4 0 4 2 2 2 2 4 4 4 4 6 6 6 6 8 8 4 8 2 6 4 6 0 8 0 10 2 10 0 16 0 12 2 16 2 18 0 22 0 12 4 22 4 22 6 24 6 24 2 18 2 24 0 26 2 26 6 22 8 14 10 32 10 24 8 26 8 28 6 28 2 26 0 30 0 32 2 36 4 36 2 34 2 32 0 38 0 38 6 30 2 32 4 30 4 3...
output:
40.219951458670
result:
wrong answer 1st numbers differ - expected: '72.4810351', found: '40.2199515', error = '0.4450969'