QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#357037 | #5104. Guardians of the Gallery | TadijaSebez | WA | 1581ms | 4192kb | C++14 | 7.2kb | 2024-03-18 17:41:09 | 2024-03-18 17:41:09 |
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(n<50){
if(ray.onSegment(seg.to) && Inside((p+seg.to)/2)){
ans=min(ans,dp[i]+dist(p,seg.to));
}
}else{
if(ray.onSegment(seg.to)){
ans=min(ans,dp[i]+dist(p,seg.to));
}
}
}
}
}
}
printf("%.12lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 4176kb
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: 3ms
memory: 4184kb
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: 3912kb
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: 6ms
memory: 3896kb
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: 4192kb
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: 0ms
memory: 3888kb
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: 1ms
memory: 3952kb
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: 1ms
memory: 3868kb
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: 4184kb
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: 4048kb
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: 0ms
memory: 3884kb
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: 2ms
memory: 4180kb
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: -100
Wrong Answer
time: 1581ms
memory: 3936kb
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:
1066.000533953212
result:
wrong answer 1st numbers differ - expected: '1695.1865730', found: '1066.0005340', error = '0.3711603'