pA - White Water Rafting
給一個簡單內多邊形和外多邊形，求中間圍起來的部份，寬度最小為多少。\
枚舉每個邊的組合，求兩線段之距離，取最小者，複雜度為 $\mathcal{O}(n^2)$。
pB - Colliding Traffic
在平面上，有 $n$ 個點，各自以定速朝定方向前進 (i.e 射線)，當兩個點間距 $< r$ 時，定義他們 collide ，想問第一個 collide 發生在什麼時候。 枚舉每條射線的組合，先看距離是否已小於 $r$ ，如果是就輸出 $0$。 不是的話，由兩條射線的參數方程相減得到其距離的參數方程，
\[
\vec{d}_{i,j} = (\vec{s}_j - \vec{s}_i) + (\vec{v}_j - \vec{v}_i) t \quad (\, \vec{s} \; \text{為起始位置}\,)
\]
找是否存在 $t > 0$ 滿足 $|\vec{d}_{i,j}| \leq r$，然後從所有射線組合中，找出最小的 $t$，複雜度為 $\mathcal{O}(n^2)$。
double get_collision_t(Obj i,Obj j,double r_sq){
double a,b,c;
a = i.vel.distance_square(j.vel);
b = (j.pos - i.pos).dot(j.vel - i.vel);
c = i.pos.distance_square(j.pos) - r_sq;
double D = b*b - a*c;
if(isz(D)){
return (-b/a);
}
else if(D<0){
return -100;
}
else{
if(b+sqrt(D) > 0)
return ((-b+sqrt(D))/a);
else
return ((-b-sqrt(D))/a);
}
}
pC - Pesky Mosquitoes
圖上散落了一些點，給定一個定直徑 $d$ 的圓，想找出最多可以蓋住幾個點。\
觀察到若想蓋住最多點的話，至少有兩個點會在圓的邊上(否則總是可以再移動，
看能否再蓋住更多點)。
枚舉所有點的組合，找出過那兩點 $A, B$ 且直徑為 $d$ 的圓，再來看剩下的點是
否在此圓裡面，複雜度為 $\mathcal{O}(n^3)$。\
而找圓心的話，算是高中數學的範疇，應該很簡單。但注意到這樣定義的圓會有兩個，方便起見我們統一
一個方向，法向量指向 $\overrightarrow{AB}$ 的右邊 (如此算 $\overrightarrow{BA}$ 時，就會得到另一個圓了)。
pD - Unusual Darts
吃了兩個 WA ，真難玩…
pE - Meltdown
我看我是沒理解題意…
comments powered by Disqus