https://cn.vjudge.net/problem/UVALive-4064
简单的极角排序应用，枚举每个点作为角点，然后按照角度顺时针枚举另一个点，在这个过程中递推记录下对于枚举的点有多少个钝角/直角出现。由于一个钝角/直角唯一的对应一个钝角/直角三角形，因此最后只需要把C(n,3)-钝角数量作为答案即可。
坑点：lrj的书上和各位dalao的blog都说的是锐角或直角，呵呵，wa了两个多小时最后翻别人代码发现是只能锐角不能直角，服了，改了就过了，也不知道网上这么多人都写得锐角或者直角是怎么写出来只能锐角的代码的。
继续阅读“[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks”
题目链接 https://cn.vjudge.net/problem/UVA-1634
最近有把紫书dp这一章的习题搞完的打算。。。这个题本来看vjudge上就不到20个人做想放弃的，强迫症导致开了题就得ac。
其实和之前的那个极角排序的题目感觉很像，只不过如果还是按照那个思维来的话会遇到一个问题无法解决，就是不能在保证为凸多边形的情况下满足无后效性。。。这个光从样例就可以试出来，所以就卡了半小时没有头绪。索性直接搜了。。。但是没想到这个搜题解讲的也很迷而且做的人很少，就直接去vjudge看了代码，看到dp是二维的和转移方程顿时懂了，和之前那个题一样都是枚举左下角的点，但是这个要求dp的时候考虑两维，也就是dp[i][j]表示当前左下角点对应的以i为顺时针倒数第一个点（也就是紧挨着枚举点s的点）且以就j为顺时针倒数第二个点的最大多边形面积。 继续阅读“[紫书][DP][计算几何] UVA1634 The Picnic”
题目链接 https://cn.vjudge.net/problem/UVA-11529
（复习期末期间日常的小题
想到了考虑每个点被多少个三角形包围，但是没想到怎么算。。。主要还是计算几何太萎le，完全没有想到可以极角排序处理emmm。
具体的就是，考虑每一个点被多少个三角形包含，但是直接考虑也不好计算，可以考虑反向计算出不被多少个三角形包含，这个计算就要用到极角排序了。。。循环遍历每个点，在每个xi点，都对所有的其他点（姑且称为角点吧）相对于这个xi点的极角做一个排序，然后利用三角形的性质，选一个方向（顺时针或者逆时针都行），依次考虑“以每个角点为最小极角与之角度差小于pi的最大角度点之间有多少个点“，可能难以理解，画个图就好了，算出来点的数量p（p包含最大的那个点）之后C(p,2)就是“包含当前最小角点的所有的不覆盖xi点的三角形数量”，依次累加就好了。。。
另外，画个图就会发现，还需要考虑圆周转一圈的情况，所以要把排序后的极角数组复制一遍，而且复制出来的这个数组每个元素还要加2pi！（这个自己试试就知道了）
然后就是找最大点的步骤要小心，很容易写错。。莫名其妙，也可能是我最近复习微机原理复习傻了。 继续阅读“[数学][计算几何][极角排序][递推] UVA 11529 Strange Tax Calculation”
