Earth Observation with a Mobile Robot Team (AOJ1139)

AOJ-ICPC Programming 幾何

バグらせた.死にたい.
まず最短で交わるタイミングだけ求めればいいとかいう嘘を書いてしまったのが問題なんだよなあ(すぐ修正できたけど)
あと二次方程式間違えてたのは♨.
微妙に7日に間に合わなかった・・・
あと幾何ではない問題として,人aとbが会えるタイミングが区間で与えられる.あったら名刺を交換できる.aの名刺を各人がもらえるタイミングを求めよ.という問題は,dijkstra N logN * (時間t以上ではじめてxとyが出会う時間 を求める計算量) でやるのがよい.(それはそう,でも最短とはちょっと違うから考えてしまった) まあこの問題だとN^2でいいのでそれでやった.

こういう系はライブラリいらないから好きって言って何回バグらせてんだ～.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef double D;
typedef complex<D> P;
D inf=1e50;
D dot(P x,P y){return real(x*conj(y));}
int N,T,R,n[100];
string st[100];
D t[100][1001];
P v[100][1001],p[100][1001];
D fi(D x){
	if(abs(x)<1e-9) return 0;
	return x;
}
typedef pair<D,D> Pdd;
vector<Pdd> segs[100][100];
void fix(vector<Pdd> vc){
	if(vc.empty()) return;
	sort(all(vc));
	vector<Pdd> ret;
	D l=vc[0].fs,r=vc[0].sc;
	for(Pdd p:vc){
		if(r<p.fs){
			ret.pb(Pdd(l,r));
			l=p.fs,r=p.sc;
		}else{
			chmax(r,p.sc);
		}
	}
	ret.pb(Pdd(l,r));
	vc=ret;
}
D fst(vector<Pdd> vc,D t){
	int N=vc.size();
	int id=lower_bound(all(vc),Pdd(t,0))-vc.begin()-1;
	if(id>=0&&vc[id].fs<t&&t<vc[id].sc) return t;
	id++;
	if(id==N) return inf;
	return vc[id].fs;
}
int main(){
	while(true){
		cin>>N>>T>>R;
		if(N==0) break;
		rep(i,N) rep(j,N) segs[i][j].clear();
		rep(i,N){
			cin>>st[i];
			int j=0;
			while(true){
				int vx,vy;
				cin>>t[i][j]>>vx>>vy;
				if(j==0) p[i][0]=P(vx,vy);
				else{
					v[i][j-1]=P(vx,vy);
					p[i][j]=p[i][j-1]+v[i][j-1]*(t[i][j]-t[i][j-1]);
				}
				if(t[i][j]==T) break;
				j++;
			}
			n[i]=j;
		}
		rep(a,N) rep(b,a){
			rep(i,n[a]) rep(j,n[b]){
				D tl=max(t[a][i],t[b][j]);
				D tr=min(t[a][i+1],t[b][j+1]);
				if(tl>tr) continue;
				P s=(p[a][i]-t[a][i]*v[a][i])-(p[b][j]-t[b][j]*v[b][j]),dv=v[a][i]-v[b][j];
				D A=fi(norm(dv));
				D B=2.0*dot(s,dv);
				D C=fi(norm(s)-R*R);
				if(A==0){
					if(C<=0) segs[a][b].pb(Pdd(tl,tr));
					continue;
				}
				D det=B*B-4*A*C;
				if(det<0) continue;
				D x=(-B-sqrt(det))/2.0/A,y=(-B+sqrt(det))/2.0/A;
				chmax(tl,x);chmin(tr,y);
				if(tl<tr) segs[a][b].pb(Pdd(tl,tr));
			}
			fix(segs[a][b]);
			segs[b][a]=segs[a][b];
		}
		bool done[100]={};
		D d[100];
		rep(i,N) d[i]=inf;
		d[0]=0;
		rep(i,N){
			int mn=-1;
			rep(j,N) if(!done[j]&&(mn<0||d[j]<d[mn])) mn=j;
			if(mn<0||d[mn]==inf) break;
			done[mn]=1;
			rep(j,N) if(!done[j]){
				D x=fst(segs[mn][j],d[mn]);
				chmin(d[j],x);
			}
		}
		vector<string> ans;
		rep(i,N) if(d[i]<T) ans.pb(st[i]);
		sort(all(ans));
		for(string s:ans) cout<<s<<endl;
	}
}