
POJ 3689 Equations 题解 《挑战程序设计竞赛》
POJ 3689 Equations 对偶线性规划:n维参数向量满足两个等式,求另一个参数向量的极大值? 3.6与平面和空间打交道的计算几何 凸包 首先形式化描述该线性规划(线性规划与对偶问题的一般化详见附录): 原...
POJ 3689 Equations 对偶线性规划:n维参数向量满足两个等式,求另一个参数向量的极大值? 3.6与平面和空间打交道的计算几何 凸包 首先形式化描述该线性规划(线性规划与对偶问题的一般化详见附录): 原...
POJ 3246 Game 凸包游戏:N个点中去掉一个得到N个点集,求这些点集构成的凸包的最小面积? 3.6与平面和空间打交道的计算几何 凸包 不难想到去掉的点一定是凸包的顶点,于是就可以2000MS+水过去: #i...
POJ 2079 Triangle 凸包三角:求N个点组成的三角形的最大面积? 3.6与平面和空间打交道的计算几何 凸包 不难想到最大三角形一定由凸包的顶点构成,难点在于怎么搜索。O(N^3)枚举会超时,旋转卡壳法O...
POJ 3608 Bridge Across Islands 跨岛大桥:在两个凸包小岛之间造桥,求最小距离? 3.6与平面和空间打交道的计算几何 凸包 这题原始数据已经是凸包(convex polygons)了,所以...
POJ 1912 A highway and the seven dwarfs 高铁与七个小矮人:侏儒岛上有N栋房子,组成一个社区。现给定一条高铁,问该高铁是否分割了社区? 3.6与平面和空间打交道的计算几何 凸包 ...
POJ 1113 Wall 墙:有个愚蠢的皇帝要你造墙将城堡围起来,城堡的顶点有N个,墙必须离城堡的边至少L单位远,并且墙的总长度尽量小。求此长度? 3.6与平面和空间打交道的计算几何 凸包 因为墙的长度要尽量短,所...
POJ 2482 Stars in Your Window 数星星:夜空有n个星星,坐标(x,y)亮度c。用长W宽H的窗户去套,问能套住的星星的亮度之和的最大值? 3.6与平面和空间打交道的计算几何 平面扫描 引子还...
POJ 3293 Rectilinear polygon 直角多边形:给定N个点,问是否能组成直角多边形(每个顶点都与另外两个顶点构成直角,每条边都平行于坐标轴),并求出周长? 3.6与平面和空间打交道的计算几何 平面扫描&nb...
POJ 3168 Barn Expansion 扩地:有N块不重叠的矩形地,由左下角(A,B)和右上角(C,D)决定。如果两块地的边或角相交,则两块地都无法扩大。求多少地可以扩大? 3.6与平面和空间打交道的计算几何 平面扫描&...
AOJ 2201 Immortal Jewels 求婚:有个贵族向一个贫穷的公主求婚,公主提出条件,需要一种“永生宝石”做嫁妆。这种宝石极其稀有,而且极易损毁,所以开采时需要特别小心。如图: 矿工需要使用一种特殊的金属棒开采,宝石呈圆形,矿...