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

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

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

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

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

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

2015-02-10阅读(4220)评论(0)

POJ 1418 Viva Confetti 礼花：Confetti 是一些大小不一的彩色圆形纸片，人们在派对上、过节时便抛洒它们以示庆祝。落在地上的Confetti会堆叠起来，以至于一部分会被盖住而看不见。给定Confetti的尺寸和位置...

2015-02-08阅读(5768)评论(0)

POJ 1981 Circle and Points 套圈：平面上有N个点，用单位圆去套，最多能套几个？ 3.6与平面和空间打交道的计算几何  极限情况  所谓极限情况就是单位圆上有两个点，稍微动一下就会损失一个点，覆盖...

2015-02-08阅读(3963)评论(2)

AOJ 2230 How to Create a Good Game 游戏设计：国际游戏公司ICPC (International Company for Playing and Competing)要加工一个游戏，该游戏的关卡是一个有向无...

2015-02-07阅读(4090)评论(2)

AOJ 2266 Cache Strategy 擦车策略：Google Code Jam区域赛上，坐在右前方的男人ID叫lyrically。东京大学时代的记忆中，记得有个朋友也用类似的ID。不过我的朋友都是萌妹子，我记忆中的lyricall...

2015-02-05阅读(3744)评论(2)

POJ 3422 Kaka's Matrix Travels 环游矩阵：N*N的地图上每格都有分数，分数只能获取一次。有人从左上方开始，每次向右或下移动一格，到右下方为止，记为一次环游。问第K次环游后累计分数的最大值？ 3.5借助水...

2015-02-05阅读(5071)评论(2)

POJ 2195 Going Home 回家：N*M的地图上有等量的人和房子，人每移动一格花费1。求一人一房最小费用？ 3.5借助水流解决问题的网络流  最小费用流  依然是很常规的最小费用流，新建源点s，从s到每个人建...

2015-02-01阅读(3959)评论(1)

POJ 3068 "Shortest" pair of paths 危险品：N个仓库由M条有向边连接，每条边都有一定费用。将两种危险品从0运到N-1，除了起点和终点外，危险品不能放在一起，也不能走相同的路径。求最小费用？...