SRM 293 DIV1 Hard CirclesOfDestruction

問題 Editorial

問題

xSize*ySizeの矩形領域がある。
領域内のいくつかの場所(x[i], y[i])に「膨張する」円がある。それは、時間tのとき半径tになる。今(時間0)では限りなく小さい。
自分は今(時間0)(px, py)にいる。自分はどんな方向にも1の速さで移動することが出来る。
ここから、領域の端(上,左,右,下のどこでもよい)へ行きたい。
しかし、移動途中に膨張する円を踏んではいけない(ただし円のエッジの上はOK)。
このとき、領域の端へ移動するまでの最短時間を求めよ。領域の端へ行けない時は-1を返せ

• 1 <= xSize, ySize <= 1000
• 1 <= |x| = |y| <= 50
• 0 <= px, x[i] <= xSize
• 0 <= py, y[i] <= ySize
• (x[i], y[i])の全てと(px, py)のそれぞれは同じでない
• 領域の端へ移動することが出来る場合、その移動経路のどこでも円から1e-6以上離れた場所にいる移動経路が存在する

解答

Editorialを見た。
結論から言ってしまうと「終点まで直線の経路で行ける <-> 円の中心と終点との距離の最小値 >= 自分と終点との距離」という定理が成り立つ。

• まず"→"。
  • 対偶を取る。
  • 自分は終点まで行くのにその距離分の時間がかかる。
  • 円はそれより小さい時間で既に終点を覆っている。なので行けない。
• 次に"←"
  • 背理法。
  • もし行けないとしたら円とぶつかる位置と時間があるはずである。
  • その位置から自分の経路の直線上に自分と同じ速さで通らせてみる。ここでぶつかった所からのその経路は円に含まれている(円の中に小さい円を描くイメージ)。
  • 自分が終点に来た時、それも終点に来ていて、つまり終点が円に含まれている。
  • 円に含まれているということは円の中心と終点との距離がその時間未満である。その時間というのは自分と終点との距離である。これは前提の否定である。

さて、終点がわかれば判定と距離の測定ができることはわかったが、終点はどのように決めればよいか？
これは円に当たらないギリギリのところを取ればいい。それは単純な式を解けばわかる。また、自分から壁への最短も最適になりうるのでそれも判定する

コメント

こんな自明な感じの初等的なものも結構考えないと理解できないなんて自分数学ひどすぎる。
証明風なものは雑で不完全だし、もっとエレガントな考え方もあるんじゃないかな。
しかし自分にとって一見自明でないこの問題は面白いな

コード

#include <vector>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define EPS 1e-9
using namespace std;
typedef vector<int> vi;  
struct CirclesOfDestruction {
	double oneWall(int width, int px, int py, const vi &cx, const vi &cy) {
		//上の辺
		int n = cx.size();
		double r = 1e99;
		//最適な所はどれかのギリギリか最短のところ
		rer(i, 0, n) {
			double x;
			if(i == n || cx[i] == px) {
				x = px;
			}else {
				//cy[i]^2 + (cx[i]-x)^2 = py^2 + (px-x)^2
				x = ((cy[i]*1.*cy[i] + cx[i]*1.*cx[i]) - (py*1.*py + px*1.*px)) / (cx[i] - px) / 2;
				x = max(x, 0.);
				x = min(x, (double)width);
			}
			bool ok = true;
			rep(j, n)
				ok &= hypot(cx[j]-x, cy[j]) >= hypot(px-x, py)-EPS;
			if(ok) r = min(r, hypot(px-x, py));
		}
		return r;
	}
	double exitTime(int xSize, int ySize, int px, int py, vector <int> x, vector <int> y) {
		double r = 1e99;
		int n = x.size();
		rep(rotate, 2) {
			rep(hflip, 2) {
				r = min(r, oneWall(xSize, px, py, x, y));
				rep(i, n) y[i] = ySize - y[i];
				py = ySize - py;
			}
			swap(xSize, ySize);
			swap(px, py);
			x.swap(y);
		}
		return r == 1e99 ? -1 : r;
	}
};