2013年4月1日 星期一

最小圓覆蓋

好久沒有學習新東西了,今天因為剛好要用到 (poi的plot)

所以就順便學一下了,如果有敘述不清,歡迎糾正>_____<

=====================================


Lv 1. Naiwny Algorytm(樸素算法) O(n^4)


枚舉三個點,做出一個圓圈圈,看有沒有覆蓋所有的點點點點


Lv 2. Zhang Jiao(張角法) O(n^3)



       想法其實也很簡單,就是枚舉兩個點(如圖中的A, B)當圓周上的點,接下來,因為離這個圓越遠的角一定越小,所以找出在AB線段上面跟下面兩種的最小角點(也就是像圖中的C與D),如果這兩個角alpha + beta >= pi 的話,你就得到一個包含圓了(太小就變成一個怪怪的橢圓了),雖然要特別判一下,就是如果max(alpha, beta) >= pi,就可以把AB當成直徑,如果 < pi,就拿這三個點做圓(必定唯一)。

接下來就要進行大進化!

Lv 9999999. Venusaur(廟哇花) O(n)

       其實叫隨機增量法 A___A ,利用一個神定理和Random的特性,以最樸素作法少三個冪次的超神演算法。(雖然常數頗大)

神定理:假設{p1, p2 ... pi-1},形成一個最小包含圓,若pi不在這個圓內,那麼{p1, p2 ... pi}所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 產生一個最小包含圓:
加入 pi 之後(不是M_PI,只是p的第i項XDDD)
--------------------------------------------------------------------
1. pi 在圓內or圓上:爽!什麼毛都不用做
2. pi 在圓外:對於{p1 ~ pi}的最小包含圓,pi一定在圓上(依據神定理)

=====================================

至於他發生2.的這件事的機率是多少呢!因為1~i ,普通情況只會有三個點在圓上,所以機率是 3 / i !!!!!!!!!!! 接下來你輕鬆亂推廣神定理。

亂推神定理:假設{p1, p2 ... pi-1},且點 x 在圓周上,形成一個最小包含圓,若pi不在這個圓內,那麼{p1, p2 ... pi}且點 x 在圓周上,所產生的最小包含圓一定有pi在圓周上。

{p1 ~ pi-1} 且圓周上有點x,產生一個最小包含圓:
加入 pi 之後
--------------------------------------------------------------------
1. pi 在圓內or圓上:爽!什麼毛都不用做
2. pi 在圓外:對於{p1 ~ pi}且x在圓周上的最小包含圓,pi一定在圓上(依據亂推神定理)


=====================================


相同的,發生2.的機率還是3 / i 或更低。這時你已經確定有兩個點在圓周上了。
接下來,反正就再做一次亂推神定理,就有三個確定的點啦~~~~~~~~~

三個點形成一個圓~所以就結束了。

至於為什麼是O(n),請自行做點小小的計算吧。

2013年3月27日 星期三

2013年3月22日 星期五

2013年3月4日 星期一

USACO 2012 三月 金組

第一題:

關鍵:


這個數量約等於 nlgn,因為你在建表的時候,大致像下面那樣



for(int i = 1; i < N; i++)
        for(int j = i; j < N; j += i) P[j].PB(i); 

這樣子的數量級差不多是O(nlgn),因為 sum of 1/x 是 lgn。

所以:2^質因數個數 <= 因數的數量 <= nlgn

至於第一項是哪裡來的呢?是排容原理。

總之因數數量的總和其實是很小的,要注意這一個地方。

第二題:

相信大家都寫過,這題直鏈的版本,想通就解決了,較為簡單的一個題目。

第三題:

       我寫的是一個暴力搜的方法,並用目前答案去做剪枝,但這種作法在暴力方式是1*2*3*4*5*6*7...這樣子會比較有效。

       我一開始寫的暴力方式 n*n-1*n-2...,就會顯得沒有什麼意義,以後要多想由小到大的方法,會比較好Cut。

      官方題解不知道是在寫什麼毛,明天再去看看。

2013年2月28日 星期四

Codeforces 198 C. Delivering Carcinogen

Codeforces 的題目還蠻有品質保證的

很不錯的幾何題。不知道怎麼做就,二分搜

假設答案是 t 秒,那麼 > t 秒的都可以(先走到跟他一樣,而且V > Vp),利用這個性質來二分搜。

所以現在那個一直在繞圈圈的行星,被我們固定住

你只要找到所在位置與該行星的最短距,就解決了

直線永遠是最短距離,所以假如你不會穿越中間的圓圈,就直接拿他們的直線距離。

假設有穿越中間的圓圈,可以知道走切線再走圓弧再走切線,會是最短距離,

所以把他們一一算出來之後,就成功了。

=======================================

子問題-

1. 判斷有沒有穿越中間:直線與中心的距離 <= r 且OAB和OBA都是銳角

2. 直線與中心的距離:算外積後(平行四邊形面積),再除掉底 = 高 

3. 判斷兩個向量是否形成銳角:內積後,正的為銳角,負的為鈍角

4. 切線的長度:OA^2 - R^2

5. 圓弧的角度:設切點是C, D,設高是M,
若BOA是銳角: (BOM-BOD-AOC),若BOA是鈍角: (180 - BOM - BOD - AOC)

Codeforces 198E. Gripping Story

線段樹的變形真的很經典

這題要做的就是我們希望可以把 距離 <=  r 的區段

重量都小於等於力量的物質挑出來,放入queue裡

每一個物質都有兩個變量,距離以及重量

要對 <= 某距離內,找出 <= 某重量 的物質

這時,我們要用到一個很基本的概念:區段樹

就是一個線段樹,但是他的每一個節點,不是單單包含一個值

而是包含了這個區段的所有元素!

這麼看的話,感覺還挺崩潰的,但是可以知道每個元素只會被lgn個包含

所以元素數量是 NlgN ,非常的好用

有了這個方向之後,是否就很簡單了呢?答案是:Yes

只要讓那個區段的值都是由小排到大的,之後在query時

就從前面開始取出即可

(我是用Set去讓他由小到大的,整體複雜度nlg^2n,但只要質量小的放到質量大的,就可以用nlgn的時間,解出來了)

想要看code,可以直接去codeforces,上面找。