作者chhsiao (bye~)
看板ACMCLUB
標題Re: 真是太亂了 @"@
時間Mon Sep 13 18:57:08 2004
※ 引述《smartboy (小光光)》之銘言：
: ※ 引述《sophialiege (爬回來了)》之銘言：
: : 方案二
: : 用N-space的Convex Hull來解,不過很怕求點上precision的問題產生
: 給一堆不等式, 要怎麼用 convex hull 來解?
: (先討論二維的就好)
: 類似這個問題同時問 chhsiao 的旋轉法:
: 要怎麼做二維的題目?
那就變成檢查某條直線與解集合有沒有截線段
因此可以把這條直線轉成 x 軸, 看與其他直線的交點能不能圍成一個區域
ex.
假設有三條直線，其餘兩條與 L 交於 A, B
-------A---------B----------- L
如果解區域是 >= A 且 <= B
就表示有截線段, 因此 L 是一條臨界線
: 二維的線性規劃我記得有簡單的作法, 不過忘是怎樣了 XD
: 這題我想到的是, 若會 simplex algorithm 的話
: 令 input 是 f_i(x)<=c_i, 1<=i<=n
: 則
: for i=1 to n
: 用 simplex 求 {
: maximize f_i(x)
: subject to f_j(x)<=c_j, 1<=j<=n
: }
: 解出 x_0, 若 f_i(x_0)<c_i 則 equation f_i 可以丟掉
: 不過不會 simplex algorithm 的問題比較大...:P
--
n;main(i){return n?i<2?i:main(i-1)+main(i-2):
scanf("%d",&n)&&printf("%d\n",n>0?main(n):0);}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.66