作者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