2015-02-27阅读(4793)评论(0)

POJ 3689 Equations 对偶线性规划：n维参数向量满足两个等式，求另一个参数向量的极大值？ 3.6与平面和空间打交道的计算几何  凸包  首先形式化描述该线性规划（线性规划与对偶问题的一般化详见附录）： 原...

2015-02-26阅读(3860)评论(0)

POJ 3246 Game 凸包游戏：N个点中去掉一个得到N个点集，求这些点集构成的凸包的最小面积？ 3.6与平面和空间打交道的计算几何  凸包  不难想到去掉的点一定是凸包的顶点，于是就可以2000MS+水过去： #i...

2015-02-25阅读(4133)评论(0)

POJ 2079 Triangle 凸包三角：求N个点组成的三角形的最大面积？ 3.6与平面和空间打交道的计算几何  凸包  不难想到最大三角形一定由凸包的顶点构成，难点在于怎么搜索。O(N^3)枚举会超时，旋转卡壳法O...

2015-02-22阅读(5401)评论(2)

POJ 3608 Bridge Across Islands 跨岛大桥：在两个凸包小岛之间造桥，求最小距离？ 3.6与平面和空间打交道的计算几何  凸包  这题原始数据已经是凸包（convex polygons）了，所以...

2015-02-19阅读(4336)评论(0)

POJ 1912 A highway and the seven dwarfs 高铁与七个小矮人：侏儒岛上有N栋房子，组成一个社区。现给定一条高铁，问该高铁是否分割了社区？ 3.6与平面和空间打交道的计算几何  凸包  ...

2015-02-18阅读(5011)评论(0)

POJ 1113 Wall 墙：有个愚蠢的皇帝要你造墙将城堡围起来，城堡的顶点有N个，墙必须离城堡的边至少L单位远，并且墙的总长度尽量小。求此长度？ 3.6与平面和空间打交道的计算几何  凸包  因为墙的长度要尽量短，所...

2015-02-16阅读(4862)评论(0)

POJ 2482 Stars in Your Window 数星星：夜空有n个星星，坐标(x,y)亮度c。用长W宽H的窗户去套，问能套住的星星的亮度之和的最大值？ 3.6与平面和空间打交道的计算几何  平面扫描  引子还...

2015-02-15阅读(4606)评论(1)

POJ 3293 Rectilinear polygon 直角多边形：给定N个点，问是否能组成直角多边形（每个顶点都与另外两个顶点构成直角，每条边都平行于坐标轴），并求出周长？ 3.6与平面和空间打交道的计算几何  平面扫描&nb...

2015-02-14阅读(3970)评论(0)

POJ 3168 Barn Expansion 扩地：有N块不重叠的矩形地，由左下角（A,B）和右上角（C,D）决定。如果两块地的边或角相交，则两块地都无法扩大。求多少地可以扩大？ 3.6与平面和空间打交道的计算几何  平面扫描&...

2015-02-13阅读(4420)评论(1)

AOJ 2201 Immortal Jewels 求婚：有个贵族向一个贫穷的公主求婚，公主提出条件，需要一种“永生宝石”做嫁妆。这种宝石极其稀有，而且极易损毁，所以开采时需要特别小心。如图： 矿工需要使用一种特殊的金属棒开采，宝石呈圆形，矿...