判断线段与线段相交、射线与线段相交。我在做题的过程中用了二分猜答案再验证的方法。
原题地址：http://poj.org/problem?id=3347
第一象限中有若干个正方形，这些正方形都是斜着摆放的（如图）。正方形下方与 x 轴刚好相交，其横坐标为 b1, b2, …, bi. 其中 b1 的值是这样取的：当第 1 个正方形的左边端点刚好在 y 轴上时，此时该正方形下面的端点与 x 轴相交，横坐标即为 b1. 接下来的 bi 的值应该取得尽量小，并且让该正方形与之前的任何正方形没有相交，并且 bi > bi-1.
题目的要求是找出那些能够从上方竖直往下看，能够被看到的正方形，不管是能完全被看到还是部分被看到。当然这个“看”指的不是透视图的看，而是一个“直线摄像机”的那种感觉……或者可以这样想，在相当高的一个地方，一个点竖直落下之后能够砸到某个正方形（砸到一个正方形之后这个点不会弹开，而是消失掉，以免砸到其它正方形），那么这个正方形就是可以被看到的。
比较水的一道题，判断明文和密文是否有可能是匹配的。
原题地址：http://poj.org/problem?id=2159
有两种比较简单的加密方式。一种是将明文的每个字母一一映射到另一个字母，还有一种加密方式是打乱字母顺序。
这两种加密方式如果单独使用，加密的效果是非常差的。如果把这两种加密同时使用，加密效果就好多了。
问题的目标就是判断给出的明文和密文是否可能是匹配的。
第一行是密文，第二行是明文。
如果明文和密文匹配则输出“YES”，否则输出“NO”。
这道题我贡献了一个 WA, 原因第一个是我的 sgn 函数写错了，第二个是没有初始化一个变量，还好后来发现了。这道题思路上是没有错误的。
这题的计算几何方面的算法是很基础的，图论涉及到了最短路，也算是很基础的。
原题地址：http://poj.org/problem?id=1556
测试数据：http://mcpc.cigas.net/archives.html , 选择 Mid-Centrail USA 1996 相关的项来下载即可在压缩包中找到。
你需要找到一条通过一个有墙阻碍的房间的最短路。这个房间的四条边始终在 x = 0, x = 10, y = 0 和 y = 10 上。起点和终点始终在 (0, 5) 和 (10, 5) 上。墙的数量的范围是 0 ~ 18, 每堵墙上有两个门。下图展示了一个这样的房间，并且标出了从起点到终点的最短路。
这是一道基础的计算几何题，判断线段是否规范相交。
原题地址：http://poj.org/problem?id=2653
在一个平面上扔棍子，这些棍子的粗细可以忽略不计，显然，之后扔的棍子可能压在之前扔的棍子的上面（规范相交）。现在给出扔的棍子的总条数，以及每条棍子的两个端点坐标，求出扔完所有棍子之后，没有被任何棍子压住的棍子的编号。
会有多组数据。每组数据的第一行有一个整数 n, 表示这组数据有 n 条棍子。接下来 n 行，每行有 4 个数 x1 y1 x2 y2, 表示这条棍子扔到平面上之后的坐标。扔棍子的顺序与输入数据的顺序一样，先给出的棍子先被扔在平面上。如果遇到 n 为 0, 那么就结束程序。
对于每组数据，输出一行。行首需要输出“Top sticks: ”（注意冒号后面有空格），然后接着输出最后没有被压住的棍子编号。编号以逗号分隔，逗号后面要有空格。编号输出完毕之后输出一个句号。棍子的编号要以升序排列。
很基础的直线相交问题，判断两条直线的位置关系，如果相交则求交点。
原题地址：http://poj.org/problem?id=1269
题目需要我们求若干对直线的位置关系，如果规范相交则求交点，如果不是规范相交，则判断是平行还是重合。
输入数据的第一行表明有多少对直线，从第二行开始，每行有 8 个数字 x1 y1 x2 y2 x3 y3 x4 y4, 表示一对直线 (x1, y1) ~ (x2, y2), (x3, y3) ~ (x4, y4).
在输出的第一行需要输出“INTERSECTING LINES OUTPUT”，然后输出每对直线的位置关系，如果是相交则输出“POINT x y”，其中 x 和 y 是交点的两个坐标，保留两位小数。如果两条直线平行则输出“NONE”，表示两直线没有交点。如果两条直线重合则输出“LINE”，表示两条直线的公共点是整个直线。在输出的最后还要输出一行“END OF OUTPUT”。
这是一道计算几何题，挺锻炼思路的，只是这道题的精度很容易出现问题。开始我也是一直 WA, 搞了一上午。
后来我从网上下了一些说是 AC 了的代码，和我自己的代码比对，用自己写的程序来批量测了很多点，发现如果点的坐标比较大，出现精度问题的概率会小很多。但是如果点的坐标在 -10 ~ 10 之间，就会有相当高的几率出现精度问题。出现的精度问题都是在小数点第二位上，就是四舍五入害死人。经常出现 0.0049999999999 或者 0.0050000000001 之类的东西，如果保留 4 位说不定精度问题就没太大关系了。
感觉就是，两直线相交的算法要写得简单才行，还有就是取一条横线与某条线段交点的算法不能使用通用的两直线相交的算法（反正我这样用了算出的交点就比较不精确），而要自己专门列一个方程来写……
忙了一天之后，我和那个 AC 的程序比较，发现在 -10 ~ 10 之间还有大量数据不一样，都是精度问题，但是想想算了，就直接提交了。没想到 AC 了。
所以可能真的是人品问题，大家慎做此题。
水水更健康。
原题地址：http://poj.org/problem?id=2105
大家知道 IPv4 的地址是 4 段，每段是由 0 ~ 255 的整数组成的。把这 4 个段分别转换成 2 进制的表示方式，并且如果不足 8 位则在前面补上 0, 然后再依序接起来，得到一个 32 位 2 进制数。
你的任务是把 32 位 2 进制数转换成相应的 IP 地址。
计算几何中直线与线段相交的判断。主要的难点是能够想到题目可以转化成直线与线段相交的判断问题。
原题地址：http://poj.org/problem?id=3304
现在平面上有若干条线段，问能不能找到一条直线，让所有线段在这条直线上的投影至少有一个公共点。
输入数据中，第一个数 T 表示接下来有几组测试。接下来的 T 组测试数据中的每一组，第一行是一个数字 n, 表示这组数据中有几条线段，接下来的 n 行，每行有 4 个数字，表示每条线段的 (x1, y1), (x2, y2) 两个端点。
对于每组输出数据，输出是否存在那样一条直线。若存在则输出“YES!”，否则输出“NO!”。
最近比较怀念 Linux 的命令行，就安装了 Cygwin. 学校的机房教育网带宽还是比较给力，去下载 USTC 的镜像，两三兆一秒，很知足了。
以前我用 Ruby on Rails 都是在虚拟机的 Windows XP 中用 InstantRails, 感觉有点麻烦。后来慢慢了解 RoR 的时候才发现原来 RoR 还有一个迷你服务器，开发的时候什么 Apache, NginX 都是浮云了。一切从简吧。最近又从 Bazaar 转向 GIT… 好像今天废话有点多……
首先，在安装 Cygwin 的时候，应该选择安装 Devel 下的 Ruby 项，还有 Database 下的 SQLite3 之类的也最好装上。然后去下载 RubyGems. 之后，将里面的内容解压到 Cygwin 的某个临时文件夹下。cd 到那个文件夹，执行：
rubygems-1.8.7 $ ruby setup.rb
安装好后，就使用 RubyGems 安装 RoR:
~ $ gem install rails
今天做 POJ 1204 的时候，我写了一个树结构，每个节点里有一个边数组，因为一个节点最多 26 条边，所以直接开了一个 26 的数组。相当于是邻接表写的吧。然后因为节点是用 vector 存储的，当时也考虑到 vector 在重分配 (reallocation) 的时候会让该容器之前的迭代器、指针和引用失效 (A reallocation invalidates all previously obtained iterators, references and pointers to elements of the vector), 所以才选用了数组下标替代指针的方法。因为通过下标访问元素是 vector 已经封装好了的函数，无论内存如何重分配，也不会改变任何元素的下标。
但是即使是这样，程序还是在内存重新分配的时候出了问题。这个问题非常诡异，所以写一篇文章备忘一下，也请各位看官注意。
后来就让这个 Bug 给我整了两个 Time Limit Exceeded. 在 Visual Studio .NET 里调试那是一点问题也没有，而用 G++ 4.3.4 编译的时候就出问题了。
协议