QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96526 | #5104. Guardians of the Gallery | marcosk | WA | 70ms | 3804kb | C++17 | 5.6kb | 2023-04-14 09:36:24 | 2023-04-14 09:36:25 |
Judging History
answer
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
ld EPS=1e-11,DINF=1e9;
struct pt {
ld x,y;
pt(ld x, ld y):x(x),y(y){}
pt(){}
ld norm2(){return *this**this;}
ld norm(){return sqrt(norm2());}
bool operator==(pt p){return abs(x-p.x)<=EPS&&abs(y-p.y)<=EPS;}
pt operator+(pt p){return pt(x+p.x,y+p.y);}
pt operator-(pt p)const{return pt(x-p.x,y-p.y);}
pt operator*(ld t){return pt(x*t,y*t);}
pt operator/(ld t){return pt(x/t,y/t);}
ld operator*(pt p){return x*p.x+y*p.y;}
ld angle(pt p){return acos(*this*p/(norm()*p.norm()));}
pt unit(){return *this/norm();}
ld operator%(pt p){return x*p.y-y*p.x;}
bool operator<(pt p)const{return x<p.x-EPS||(abs(x-p.x)<=EPS&&y<p.y-EPS);}
bool left(pt p, pt q){return (q-p)%(*this-p)>EPS;}
bool right(pt p, pt q){return (q-p)%(*this-p)<-EPS;}
bool in(pt p, pt q){return abs((q-p)%(*this-p))<EPS;}
pt rot(pt r){return pt(*this%r,*this*r);}
pt rot(ld a){return rot(pt(sin(a),cos(a)));}
};
pt ccw90(1,0);
pt cw90(-1,0);
int sgn(ld x){return x<-EPS?-1:x>EPS;}
struct Cmp {
pt r;
Cmp(pt r):r(r){}
int cuad(const pt &a)const {
if(a.x>EPS&&a.y>=-EPS)return 0;
if(a.x<=EPS&&a.y>EPS)return 1;
if(a.x<-EPS&&a.y<=EPS)return 2;
if(a.x>=-EPS&&a.y<-EPS)return 3;
return -1;
}
bool cmp(const pt& p1, const pt& p2)const {
int c1=cuad(p1),c2=cuad(p2);
ld me=p1.y*p2.x;
ld he=p1.x*p2.y;
pt pp1=p1, pp2=p2;
if(c1==c2)return me+EPS<he || (abs(me-he)<EPS && pp1.norm()+EPS<pp2.norm());
return c1<c2;
}
bool operator()(const pt& p1, const pt& p2)const {
return cmp(p1-r,p2-r);
}
};
struct ln {
pt p,pq;
ln(pt p, pt q):p(p),pq(q-p){}
ln(){}
bool operator/(ln l){return abs(pq.unit()%l.pq.unit())<=EPS;} // 2D
pt operator^(ln l){
if(*this/l)return pt(DINF,DINF);
pt r=l.p+l.pq*((p-l.p)%pq/(l.pq%pq));
return r;
}
pt proj(pt r){return p+pq*((r-p)*pq/pq.norm2());}
};
bool seghas(pt a, pt b, pt c){
ld me=(a-b).norm();
ld he=(a-c).norm()+(b-c).norm();
return abs(me-he)<EPS;
}
bool has(vector<pt> &p, pt q){
int n=SZ(p);
fore(i,0,n)if(seghas(p[i],p[(i+1)%n],q))return true;
int cnt=0;
fore(i,0,n){
int j=(i+1)%n;
int k=sgn((q-p[j])%(p[i]-p[j]));
int u=sgn(p[i].y-q.y),v=sgn(p[j].y-q.y);
if(k>0&&u<0&&v>=0)cnt++;
if(k<0&&v<0&&u>=0)cnt--;
}
return cnt!=0;
}
ld getdist(pt p, pt dir, vector<pt> &v){
if(!has(v, p+(dir*1e-5))) return 0;
int n=SZ(v);
ld lef=1e18,rig=1e18;
pt asd=p+dir.rot(cw90);
fore(i,0,n){
pt a=v[i], b=v[(i+1)%n];
if(abs(dir%(b-a)) < EPS){
if(p.in(a,b)){
if(a==p) rig=0;
if(b==p) lef=0;
if(a.left(p,asd) && b.left(p,asd)){
if((a-p).norm() < (b-p).norm()) rig=min(rig, (a-p).norm());
else lef=min(lef, (b-p).norm());
}
}
continue;
}
pt to=ln(a,b)^ln(p,p+dir);
pt asd=p+dir.rot(cw90);
if(!seghas(a,b,to) || to.right(p,asd)) continue;
//interseco con el segmento
ld ds=(to-p).norm();
if(to==p)continue;
if(to==a){
if(b.right(p,p+dir)) rig=min(rig,ds);
else lef=min(lef,ds);
}
else if(to==b){
if(a.right(p,p+dir)) rig=min(rig,ds);
else lef=min(lef,ds);
}
else{
lef=min(lef,ds);
rig=min(rig,ds);
}
}
ld ans=max(lef,rig);
return ans;
}
vector<pt> getbox(pt p, vector<pt> &v){
auto vv=v;
sort(ALL(vv),Cmp(p));
vector<pt> ans;
fore(i,0,SZ(vv)){
if(i && vv[i].in(vv[i-1],p))continue;
pt q=vv[i];
pt dir=(q-p).unit();
ld now=getdist(p, dir, v);
pt me=p+(dir*now);
ld he=(vv[i]-p).norm();
if(he<=now+EPS){
int pos=-1,n=SZ(v);
fore(j,0,n) if(v[j]==vv[i]) pos=(j-1+n)%n;
if(!v[pos].left(p,vv[i])) swap(me,q);
ans.pb(me);
ans.pb(q);
}
else{
ans.pb(me);
}
}
ans.erase(unique(ALL(ans)),ans.end());
return ans;
}
pt getdir(pt a, pt b, pt c){
pt pr=ln(a,b).proj(c);
if(seghas(a,b,pr)) return pr;
else if((a-c).norm() < (b-c).norm()) return a;
return b;
}
const int MAXN=110;
vector<pair<int,ld>> g[MAXN];
ld bst[MAXN];
int main(){FIN;
int n; cin>>n;
vector<pt> v(n);
fore(i,0,n) cin>>v[i].x>>v[i].y;
pt me,he; cin>>me.x>>me.y>>he.x>>he.y;
//entre vertices del poligono
fore(i,0,n) fore(j,0,n) if(i!=j){
ld mx=getdist(v[i], (v[j]-v[i]).unit(), v);
ld he=(v[j]-v[i]).norm();
if(he<=mx+EPS){
g[i].pb({j,he});
}
}
//desde me hasta i
fore(i,0,n){
ld mx=getdist(me, (v[i]-me).unit(), v);
ld he=(me-v[i]).norm();
if(he<=mx+EPS){
g[n].pb({i,he});
}
}
vector<pt> box=getbox(he,v);
auto vv=v;
vv.pb(me);
fore(i,0,n+1){
bst[i]=1e18;
if(has(box,vv[i])){
bst[i]=0;
continue;
}
fore(j,0,SZ(box)){
pt p=box[j],q=box[(j+1)%SZ(box)];
pt to=getdir(p,q,vv[i]);
ld mx=getdist(vv[i], (to-vv[i]).unit(), v);
ld he=(to-vv[i]).norm();
if(he<=mx+EPS) bst[i]=min(bst[i],he);
}
}
fore(i,0,n+1) g[i].pb({n+1,bst[i]});
priority_queue<pair<ld,int>, vector<pair<ld,int>>, greater<pair<ld,int>>> q;
vector<ld> ans(n+2,1e18);
q.push({0,n});
ans[n]=0;
while(SZ(q)){
ld d=q.top().fst; int pos=q.top().snd; q.pop();
if(abs(ans[pos]-d)>EPS) continue;
for(auto x:g[pos]){
ld nd=d+x.snd;
if(nd+EPS<ans[x.fst]){
ans[x.fst]=nd;
q.push({nd,x.fst});
}
}
}
ld res=1e18;
cout<<fixed<<setprecision(10)<<ans[n+1]<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
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.0000000000
result:
ok found '29.0000000', expected '29.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3708kb
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.0000000000
result:
ok found '13.0000000', expected '13.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3764kb
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.8722825825
result:
ok found '140.8722826', expected '140.8722826', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3628kb
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.2045377025
result:
ok found '64.2045377', expected '64.2045377', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3760kb
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.2834980412
result:
ok found '72.2834980', expected '72.2834980', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
7 76 8 389 215 691 19 407 331 489 397 300 403 363 334 126 60 393 370
output:
6.6579177565
result:
ok found '6.6579178', expected '6.6579178', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
3 0 1000 1000 0 1000 1000 567 578 589 601
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
3 0 1000 0 0 1000 0 366 366 367 366
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
5 50 93 278 178 199 300 596 362 208 519 421 388 142 153
output:
175.1697593917
result:
ok found '175.1697594', expected '175.1697594', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
7 50 93 278 178 199 300 401 312 483 162 596 362 208 519 488 252 142 153
output:
289.6821398769
result:
ok found '289.6821399', expected '289.6821399', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
8 10 10 40 25 20 25 20 35 12 23 30 23 10 20 5 40 15 15 19 26
output:
25.0000000000
result:
ok found '25.0000000', expected '25.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3640kb
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.1010479070
result:
ok found '5.1010479', expected '5.1010479', error '0.0000000'
Test #13:
score: 0
Accepted
time: 70ms
memory: 3780kb
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.1865730236
result:
ok found '1695.1865730', expected '1695.1865730', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3708kb
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.3842014548
result:
ok found '1424.3842015', expected '1424.3842015', error '0.0000000'
Test #15:
score: -100
Wrong Answer
time: 30ms
memory: 3704kb
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:
982.0795880709
result:
wrong answer 1st numbers differ - expected: '2036.7557099', found: '982.0795881', error = '0.5178216'