Spotlight Movement (AOJ2625)

こういうライブラリいらないなんちゃって幾何大好きだからもっと出してくれ(例:流れ星に願いを(AOJ2586))
線分上を等直線運動する二点の最小距離 は二次式の最小化だと思える.やることがほんと少なくてすき.
でもこんなの解いても全然強くなる気しねえな・・・

追記:スライド読んだら別に二次式とかなくても三分探索でよかったね、と思ったけど最小求めるだけならこっちのほうが楽っぽい(今回はどうせ二次式出てくるし),しかし一般の場合には三分探索のほうが楽な場合もあることを覚えとこう(三分探索あまり使わないんだよな・・・)

#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;
typedef pair<P,P> L;
typedef vector<P> Pol;
D eps=1e-9,inf=1e50;
bool eq(D a,D b){return abs(a-b)<eps;}
D dot(P x,P y){return real(conj(x)*y);}
bool iSP(L s,P p){return eq(abs(s.fs-p)+abs(p-s.sc),abs(s.fs-s.sc));}
P perp(L l,P p){
	D t=dot(p-l.fs,l.fs-l.sc)/norm(l.fs-l.sc);
	return l.fs+t*(l.fs-l.sc);
}
D dSP(L s,P p){
	P q=perp(s,p);
	return iSP(s,q)?abs(p-q):min(abs(p-s.fs),abs(p-s.sc));
}
D fix(D x){
	if(abs(x)<eps) return 0;
	return x;
}
int N;
P s,t;
D r[100],l[100][11];
int K[100];
Pol pol[100];
bool is[102][102];
int main(){
	cin>>N;
	{
		int x,y;
		cin>>x>>y;
		s=P(x,y);
		cin>>x>>y;
		t=P(x,y);
	}
	rep(i,N){
		cin>>r[i]>>K[i];
		rep(j,K[i]){
			int x,y;
			cin>>x>>y;
			pol[i].pb(P(x,y));
		}
		pol[i].pb(pol[i][0]);
	}
	rep(i,N){
		rep(j,K[i]) l[i][j+1]=l[i][j]+abs(pol[i][j]-pol[i][j+1]);
		D lx=l[i][K[i]];
		rep(j,K[i]+1) l[i][j]/=lx;
	}
	rep(i,N+2) is[i][i]=1;
	rep(tt,2){
		int S=N+tt;
		P p=(tt==0?s:t);
		rep(i,N){
			rep(j,K[i]){
				if(dSP(L(pol[i][j],pol[i][j+1]),p)<r[i]) is[i][S]=is[S][i]=1;
			}
		}
	}
	rep(a,N) rep(b,a){
		D mn=inf;
		rep(i,K[a]) rep(j,K[b]){
			D la=l[a][i],ra=l[a][i+1];
			D lb=l[b][j],rb=l[b][j+1];
			D le=max(la,lb),ri=min(ra,rb);
			if(le>ri) continue;
			P d=(pol[a][i]-la/(ra-la)*(pol[a][i+1]-pol[a][i]))-(pol[b][j]-lb/(rb-lb)*(pol[b][j+1]-pol[b][j]));
			P dt=(pol[a][i+1]-pol[a][i])/(ra-la)-(pol[b][j+1]-pol[b][j])/(rb-lb);
			D A=fix(norm(dt)),B=2.0*dot(d,dt),C=norm(d);
			if(A==0){
				chmin(mn,C);
				continue;
			}
			chmin(mn,A*le*le+B*le+C);
			chmin(mn,A*ri*ri+B*ri+C);
			D m=-B/2.0/A;
			if(le<m&&m<ri) chmin(mn,A*m*m+B*m+C);
		}
		if(sqrt(mn)<r[a]+r[b]) is[a][b]=is[b][a]=1;
	}
	rep(i,N+2) rep(j,N+2) rep(k,N+2) if(is[j][i]&&is[i][k]) is[j][k]=1;
	if(is[N][N+1]) puts("Yes");
	else puts("No");
}