【写在前面】：
    其实今天本来想写道水题的...然而却非常不爽
    不愧是WF的出题人，居然可以卡掉各种优化的最大团算法，orz
【题目大意】：
    给定平面内的n个点，选出一个点集S，使得S里的所有点两两之间欧几里得距离不超过d，问|S|的最大值以及S里的点都有哪些。若答案有多种，输出任意一个。
【题目解法】：
    最大团的话还是比较显然的，然而我总是忘记最大团的剪枝，归根结底还是对剪枝本质了解不深所造成的
    所以今天来补一补最大团的算法
【最大团】：(from http://www.cnblogs.com/zhj5chengfeng/archive/2013/07/29/3224092.html)
    定义：一个无向图 G=(V，E)，V 是点集，E 是边集。取 V 的一个子集 U，若对于 U 中任意两个点 u 和 v，有边 (u,v)∈E，那么称 U 是 G 的一个完全子图。 U 是一个团当且仅当 U 不被包含在一个更大的完全子图中。G的最大团指的是定点数最多的一个团。
    解法：
    1、顺序贪婪启发式搜索算法
    2、局部搜索启发式算法
    3、智能搜索启发式算法
    4、遗传算法
    5、模拟退火算法
    6、禁忌算法
    7、神经网络算法
    8、改进蚁群算法-AntMCP
    然而这些都太高端了，作为一个NP问题显然用dfs解决一切啦(雾)
【最大团的dfs解法及剪枝】
    首先，给出朴素的dfs算法：
    初始化：从一个点 u 开始，把这个点加入到一个集合中，设为 U。遍历一遍所有和他相连的点，把他们放入另一个集合 S1 中，接下来进行第一遍 DFS
    第一遍 DFS ：从 S1 中选择一个点 u1，这个点肯定和集合 U 中的任何一个点相连。把集合 S1 中 u1 能访问到的点加入到集合 S2 中，并把 u1 加入到集合 U 中，进行第二遍 DFS
　　第二遍 DFS ：从 S2 中选择一个点 u2，这个点肯定和集合 U 中的任何一个点相连。把集合 S2 中 u2 能访问到的点加入到集合 S3 中，并把 u2 加入到集合 U 中，进行第三遍 DFS
　　第三遍 DFS ：从 S3 中选择一个点 u3，这个点肯定和集合 U 中的任何一个点相连。把集合 S3 中 u3 能访问到的点加入到集合 S4 中，并把 u3 加入到集合 U 中，进行第四遍 DFS
　　　　......
　　最底层的 DFS ：当某个 S 集合为空集的时候，DFS 结束，这时候我们就找到了一个完全子图，用这个完全子图更新我们的最大团。退出当前的 DFS，返回上层 DFS，接着找下一个完全子图，直到找完所有的完全子图
   然而这样只是最朴素的做法，当数据规模大于20时就无能为力了...
   下面是几个比较好的剪枝：
   1.顺序剪枝。每次选点时按照顺序选取，即点的选择序列是单调递增的，这样可以有效避免重复状态
   2.最优化剪枝。如果 U 集合中的点的数量+1（选择 ui 加入 U 集合中）+Si 中所有 ui 后面的点的数量 ≤ 当前最优值，不用再 DFS 了
   3.最优化剪枝。我们用f[i]表示[i,n]区间内的点构成的最大团点数，如果 U 集合中的点的数量+1（理由同上）+[ui, n]这个区间中能构成的最大团的顶点数量 ≤ 当前最优值，不用再 DFS了
   4.强大的剪枝。由于f[i]只能是f[i+1]或者f[i+1]+1（最多在[i+1,n]最大团的基础上多一个点），所以如果我们dfs到最低层时更新了答案，也就是说f[i]=f[i+1]+1了，那么此时f[i]已经最大，不可能有比f[i]更大的答案了，那么直接退出dfs
   这4个剪枝可以过掉100内的数据，下面给出代码
【随机化算法】：
    然而这道题的出题人很机智的卡掉了这种算法
    我们考虑随机化算法。我们可以每次随机化点的序列，然后贪心选择，然后就AC了
    ...这样的题目有意思吗？

阅读更多……

【写在前面】：
    这应该是我会的第二种计算几何算法(第一种显然是凸包...)，然后感觉还是要记一下比较好
【定义】：
    是解决一些与凸包有关问题的有效算法 就像一对卡壳卡住凸包旋转而得名
【对踵点】(from http://www.cnblogs.com/Booble/archive/2011/04/03/2004865.html)：
    被一对卡壳正好卡住的对应点对称为对踵点(Antipodal point)
    可以证明对踵点的个数不超过3N/2个 也就是说对踵点的个数是O(N)的
    对踵点的个数也是我们下面解决问题时间复杂度的保证
    这是旋转卡壳的关键所在(下面给几幅图):

    上第一个图是卡壳的一般情况 卡住两点 图二是卡住一条边和一个点
    由于实现中 卡住两点的情况不好处理 我们通常关注第二种情况
    在第二种情况中 我们可以看到 一个对踵点和对应边之间的距离比其他点要大
    也就是一个对踵点和对应边所形成的三角形是最大的 下面我们会据此得到对踵点的简化求法
【凸包的直径】
    显然直径一定是对踵点间的最大距离
    然后关键就是要找出对锺点
    我们可以枚举一条边，然后找出距离这条边最远的点
    然后如果依次枚举的话复杂度还是O(N^2)的
    然后我们可以发现，随着枚举的边顺时针旋转是，最远点也在顺时针移动，因此我们就可以在O(N)时间内求出答案...
【点集的最大三角形】
    显然O(N^3)可以暴力
    显然，三角形的三个顶点一定在凸包上
    其次，我们可以枚举凸包上的两个点，然后就变成求出距离这条边距离最大的点，然后就可以用求凸包直径的方法求出来了
    然而这样的时间复杂度还是O(N^3)
    但是我们又发现，假设枚举定一个点，那么第三个点是随着第二个点的顺时针旋转而旋转的，因此我们就不需要把旋转卡壳拿出来做，直接与枚举的第二个点一起做，这样时间复杂度就是O(N^2)
【点集的最大四边形】：
    其实和三角形没什么太大的区别，旋转卡壳时同时维护枚举的点两边点集的最大三角形，相加即可
    但是细节比较多，比如旋转的两个点不能在枚举两个点的同一侧，这样的话就便成凹四边形了...
【两个凸包的最近距离】：
    旋转卡壳，去第一个考虑如下的算法， 算法的输入是两个分别有m和n个顺时针给定顶点的凸多边形P和Q。
    1.计算P上y坐标值最小的顶点（称为 yminP ）和Q上y坐标值最大的顶点（称为 ymaxQ）。
    2.为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。
   此时 LP 和 LQ 拥有不同的方向， 并且 yminP 和 ymaxQ 成为了多边形间的一个对踵点对。
    3.计算距离(yminP,ymaxQ) 并且将其维护为当前最小值。
    4.顺时针同时旋转平行线直到其中一个与其所在的多边形的边重合。
    5.如果只有一条线与边重合， 那么只需要计算“顶点-边”对踵点对和“顶点-顶点”对踵点对距离。 都将他们与当前最小值
比较， 如果小于当前最小值则进行替换更新。如果两条切线都与边重合，那么情况就更加复杂了。如果边“交叠”，也就是
可以构造一条与两条边都相交的公垂线（但不是在顶点处相交）， 那么就计算“边-边”距离。 否则计算三个新的“顶点-顶
点”对踵点对距离。 所有的这些距离都与当前最小值进行比较， 若小于当前最小值则更新替换。
    6.重复执行步骤4和步骤5， 直到新的点对为(yminP,ymaxQ)。
    7.输出最小距离。
    但是细节太多了，在代码里标注了...
【凸多边形最小面积外接矩形】
    首先要明确一点：最小面积的外接矩形的某一条边一定与凸多边形的一边重合，然后就好做了
    计算全部四个多边形的端点， 称之为 xminP， xmaxP， yminP， ymaxP。
    通过四个点构造 P 的四条切线。 他们确定了两个“卡壳”集合。
    如果一条（或两条）线与一条边重合，那么计算由四条线决定的矩形的面积， 并且保存为当前最小值。 否则将当前最小值定义为无穷大。
    顺时针旋转线直到其中一条和多边形的一条边重合。
    计算新矩形的面积， 并且和当前最小值比较。 如果小于当前最小值则更新， 并保存确定最小值的矩形信息。 
    重复步骤4和步骤5， 直到线旋转过的角度大于90度。
    输出外接矩形的最小面积。
    然后就是灵活运用向量是很重要的，比如求外接矩形的面积，以及求某两条直线的交点，并且用向量可以保证精度

例题：

poj 2187最远点对模板
poj 2079最大三角形
bzoj 1069最大土地面积
poj 3608凸包最近距离
bzoj 1185最小矩形覆盖

未完待续...

阅读更多……

【题目大意】：
    给定n个人，分别戴着k类面具(k>=3,k未知)，其中戴着i类面具的人能看见第i%k+1类人的面具，给定一些人互相看到的关系，求k的最大最小值
【题目解法】：
    感觉非常神奇！！
    首先大概把图分为三种：

    1.每条边无向后为一棵树，那么就是森林中每棵树的最长链之和即为答案，最小值为3
    2.有环，然后环上点的个数一定是答案的倍数，找出环后gcd即可
    3.没有环，但是转成无向图后有环，那么我们可以发现，如果有两条链的话，那么答案为链长的差值(多条链的话以此类推)
    然后这样不好搞
    网上有种神奇的做法，就是把a可以看到b，那么连边(a,b,1) (b,a,-1)，这样子我们用c[x]表示到x点的路径权值和，然后如果一个点被到达两次，那么两次的c值相减就是环的大小，并且可以把2，3情况一起考虑
    然后就是如果又有环，又有链，那么显然链就没用了...
    然后就是细节：注意枚举的点不一定是链的顶端，所以并不是所有的点c[i]都大于1!!

阅读更多……

【题目大意】：
    求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。
【题目解法】：
    其实这是一道陈题了，但是感觉方法很赞，于是写一下加深印象
    首先，我们把式子变一下形:x^2=(r-y)(r+y)
    然后我们设d=gcd(r-y,r+y)，那么x^2=d*d*(r-y)/d*(r+y)/d
    然后我们设A=(r-y)/d  B=(r+y)/d 并且(A,B)=1（显然）
    那么原式可化为x^2=d^2*A*B，由于x^2 d^2都是完全平方数，并且(A,B)=1，所以A,B的乘积不可能为完全平方数，所以A B是完全平方数
    然后设A=a^2  B=b^2
    那么A+B=a^2+b^2=(r-y)/d+(r+y)/d=2*r/d
    所以d为2*r的约数，那么我们枚举所有2r的约数D
    所以有a^2+b^2=D
    然后一般的设a<b(因为a>b与a<b算出的答案是一样的)
    所以2*a^2<D 那么a^2<D/2，然后枚举sqrt(D/2)内所有的数a，然后判断a^2+b^2=D 且 (a*a,b*b)=1 且 a!=b，那么ans++

阅读更多……