2008 Nightman

まず警備員、不審物、建物の四隅を全列挙して純粋な幾何をしてやってから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);
}