まず警備員、不審物、建物の四隅を全列挙して純粋な幾何をしてやってからWarshall-Floyd。幾何がたるいだけ。意外と内外判定に苦労する問題です。
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; double g[220][220]; int px[10]; int py[10]; int ax[50],bx[50],ay[50],by[50]; int tx[10],ty[50]; int x[220],y[220]; int main(){ int a,b,c; int d,e; scanf("%d%d%d",&a,&b,&c); scanf("%d%d",&d,&e); for(int i=0;i<a;i++){ scanf("%d%d",px+i,py+i); x[i]=px[i]; y[i]=py[i]; } for(int i=0;i<b;i++){ scanf("%d%d%d%d",ax+i,ay+i,bx+i,by+i); x[i*4+a]=ax[i]; x[i*4+1+a]=ax[i]; x[i*4+2+a]=bx[i]; x[i*4+3+a]=bx[i]; y[i*4+a]=ay[i]; y[i*4+1+a]=by[i]; y[i*4+2+a]=ay[i]; y[i*4+3+a]=by[i]; } for(int i=0;i<c;i++){ scanf("%d%d",tx+i,ty+i); x[a+b*4+i]=tx[i]; y[a+b*4+i]=ty[i]; } for(int i=0;i<220;i++) for(int j=0;j<220;j++) g[i][j]=999999999; for(int i=0;i<220;i++)g[i][i]=0; for(int i=0;i<a+b*4+c;i++){ for(int j=i+1;j<a+b*4+c;j++){ bool ok=true; for(int k=0;k<b;k++){ if(x[i]!=x[j]){ if(x[i]>x[j]){ if(!(x[i]<=ax[k]&&x[j]<=ax[k])&&!(x[i]>=ax[k]&&x[j]>=ax[k])&&(ay[k]-y[i])*(x[i]-x[j])<=(y[i]-y[j])*(ax[k]-x[i])&&(y[i]-y[j])*(ax[k]-x[i])<=(by[k]-y[i])*(x[i]-x[j]))ok=false; if(!(x[i]<=bx[k]&&x[j]<=bx[k])&&!(x[i]>=bx[k]&&x[j]>=bx[k])&&(ay[k]-y[i])*(x[i]-x[j])<=(y[i]-y[j])*(bx[k]-x[i])&&(y[i]-y[j])*(bx[k]-x[i])<=(by[k]-y[i])*(x[i]-x[j]))ok=false; }else{ if(!(x[i]<=ax[k]&&x[j]<=ax[k])&&!(x[i]>=ax[k]&&x[j]>=ax[k])&&(ay[k]-y[i])*(x[i]-x[j])>=(y[i]-y[j])*(ax[k]-x[i])&&(y[i]-y[j])*(ax[k]-x[i])>=(by[k]-y[i])*(x[i]-x[j]))ok=false; if(!(x[i]<=bx[k]&&x[j]<=bx[k])&&!(x[i]>=bx[k]&&x[j]>=bx[k])&&(ay[k]-y[i])*(x[i]-x[j])>=(y[i]-y[j])*(bx[k]-x[i])&&(y[i]-y[j])*(bx[k]-x[i])>=(by[k]-y[i])*(x[i]-x[j]))ok=false; } } if(y[i]!=y[j]){ if(y[i]>y[j]){ if(!(y[i]<=ay[k]&&y[j]<=ay[k])&&!(y[i]>=ay[k]&&y[j]>=ay[k])&&(ax[k]-x[i])*(y[i]-y[j])<=(x[i]-x[j])*(ay[k]-y[i])&&(x[i]-x[j])*(ay[k]-y[i])<=(bx[k]-x[i])*(y[i]-y[j]))ok=false; if(!(y[i]<=by[k]&&y[j]<=by[k])&&!(y[i]>=by[k]&&y[j]>=by[k])&&(ax[k]-x[i])*(y[i]-y[j])<=(x[i]-x[j])*(by[k]-y[i])&&(x[i]-x[j])*(by[k]-y[i])<=(bx[k]-x[i])*(y[i]-y[j]))ok=false; }else{ if(!(y[i]<=ay[k]&&y[j]<=ay[k])&&!(y[i]>=ay[k]&&y[j]>=ay[k])&&(ax[k]-x[i])*(y[i]-y[j])>=(x[i]-x[j])*(ay[k]-y[i])&&(x[i]-x[j])*(ay[k]-y[i])>=(bx[k]-x[i])*(y[i]-y[j]))ok=false; if(!(y[i]<=by[k]&&y[j]<=by[k])&&!(y[i]>=by[k]&&y[j]>=by[k])&&(ax[k]-x[i])*(y[i]-y[j])>=(x[i]-x[j])*(by[k]-y[i])&&(x[i]-x[j])*(by[k]-y[i])>=(bx[k]-x[i])*(y[i]-y[j]))ok=false; } } } double S=(double)(x[i]+x[j])/2; double T=(double)(y[i]+y[j])/2; for(int k=0;k<b;k++){ if((double)ax[k]+0.00001<=S&&S<=(double)bx[k]-0.00001&&(double)ay[k]+0.00001<=T&&T<=(double)by[k]-0.0001)ok=false; } if(ok)g[i][j]=g[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } } // for(int i=0;i<a+b*4+c;i++,printf("\n")) // for(int j=0;j<a+b*4+c;j++) // printf("%.2f ",g[i][j]>10000?-1:g[i][j]); for(int k=0;k<a+b*4+c;k++) for(int i=0;i<a+b*4+c;i++) for(int j=0;j<a+b*4+c;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); double ans=0; for(int i=0;i<c;i++){ double m=999999999; for(int j=0;j<a;j++)m=min(m,g[j][i+a+b*4]); ans+=m; } printf("%.3f\n",ans*2); }
