AOJ 2179: Safe Area

これはかなり簡単だと思います。イベントをどうしてこうするだけ。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
//略
Pt L[110];
Pt R[110];
Pt vec[110];
double t[110];
int main(){
	int W,H,N;
	double r;
	while(scanf("%d%d%d%lf",&W,&H,&N,&r),W){
		for(int i=0;i<N;i++){
			double X1,X2,Y1,Y2;
			scanf("%lf%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2,t+i);
			L[i]=Pt(X1,Y1);
			R[i]=Pt(X2,Y2);
			vec[i]=(R[i]-L[i])*Pt(0,1);
			vec[i]=vec[i]/(vec[i].ABS())*(t[i]+r);
		}
		vector<Pt> hb;
		hb.push_back(Pt(r,r));
		hb.push_back(Pt(W-r,r));
		hb.push_back(Pt(r,H-r));
		hb.push_back(Pt(W-r,H-r));
		vector<pair<Pt,Pt> > lines;
		for(int i=0;i<N;i++){
			lines.push_back(make_pair(L[i]+vec[i],R[i]+vec[i]));
			lines.push_back(make_pair(L[i]-vec[i],R[i]-vec[i]));
		}
		lines.push_back(make_pair(hb[0],hb[1]));
		lines.push_back(make_pair(hb[0],hb[2]));
		lines.push_back(make_pair(hb[3],hb[1]));
		lines.push_back(make_pair(hb[3],hb[2]));
		for(int i=0;i<lines.size();i++)for(int j=i+1;j<lines.size();j++){
			if(iLL(lines[i].first,lines[i].second,lines[j].first,lines[j].second)!=1)continue;
			Pt p=pLL(lines[i].first,lines[i].second,lines[j].first,lines[j].second);
			if(r-EPS<p.x&&p.x<EPS+W-r&&r-EPS<p.y&&p.y<EPS+H-r)hb.push_back(p);
		}
		bool ok=false;
	//	printf("%d ",hb.size());
		for(int i=0;i<hb.size();i++){
			bool OK=true;
			for(int j=0;j<N;j++){
				if(dLP(L[j],R[j],hb[i])<t[j]+r-EPS)OK=false;
			}
			if(OK)ok=true;
		}
		if(ok)printf("Yes\n");
		else printf("No\n");
	}
}