QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356650 | #5104. Guardians of the Gallery | TadijaSebez | WA | 6ms | 4204kb | C++14 | 6.8kb | 2024-03-18 06:48:35 | 2024-03-18 06:48:35 |
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);
}
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);
if(!hasR)return line(from,L);
if(a.offs(L)<a.offs(R)){
return line(from,R);
}else{
return line(from,L);
}
}
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));
}
}
}
}
}
}
printf("%.12lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 3896kb
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: 4ms
memory: 4068kb
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: 4ms
memory: 4204kb
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: 3976kb
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: 5ms
memory: 3992kb
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: 4060kb
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: 3888kb
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: 3944kb
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: 3896kb
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: 1ms
memory: 3960kb
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: -100
Wrong Answer
time: 1ms
memory: 4184kb
input:
8 10 10 40 25 20 25 20 35 12 23 30 23 10 20 5 40 15 15 19 26
output:
25.098824189185
result:
wrong answer 1st numbers differ - expected: '25.0000000', found: '25.0988242', error = '0.0039530'