基本的叉积、点积和凸包等东西就不多说什么了，网上一搜一大堆，切一些题目基本熟悉了就差不多了。
一些基本的题目可以自己搜索，比如这个blog：http://blog.sina.com.cn/s/blog_49c5866c0100f3om.html
接下来，研究了半平面交，思想方法看07年朱泽园的国家队论文，模板代码参考自我校大牛韬哥：
一些半平面交的题目：
POJ 3335 Rotating Scoreboard
http://acm.pku.edu.cn/JudgeOnline/problem?id=3335
POJ 3130 How I Mathematician Wonder What You Are!
http://acm.pku.edu.cn/JudgeOnline/problem?id=3130
POJ 1474 Video Surveillance
http://acm.pku.edu.cn/JudgeOnline/problem?id=1474
知识点：半平面交求多边形的核，存在性判断
POJ 1279 Art Gallery
http://acm.pku.edu.cn/JudgeOnline/problem?id=1279
半平面交求多边形的核，求核的面积
POJ 3525 Most Distant Point from the Sea （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3525
给出一个多边形，求里面的一个点，其距离离多边形的边界最远，也就是多边形中最大半径圆。
解法：可以使用半平面交+二分法解。二分这个距离，边向内逼近，直到达到精度。
POJ 3384 Feng Shui （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3384
半平面交实际应用，用两个圆覆盖一个多边形，问最多能覆盖多边形的面积。
解法：用半平面交将多边形的每条边一起向“内”推进R，得到新的多边形，然后求多边形的最远两点。
POJ 1755 Triathlon （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1755
半平面交判断不等式是否有解。注意不等式在转化时正负号的选择，这直接影响到半平面交的方向。
POJ 2540 Hotter Colder
http://acm.pku.edu.cn/JudgeOnline/problem?id=2540
半平面交求线性规划可行区域的面积。
POJ 2451 Uyuw’s Concert
http://acm.pku.edu.cn/JudgeOnline/problem?id=2451
Zzy专为他那篇nlogn算法解决半平面交问题的论文而出的题目。
(以上题目来自别人的blog，后面还有几题是我自己找到的)
<address> POJ 1271 Nice Milk</address> <address> http://poj.org/problem?id=1271</address> <address> 黑书习题</address> <address></address> <address> </address> <address> UVA 11722 Joining with Friend</address> <address> http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2769</address> <address> 概率问题，这个规模用半平面交有点浪费，不过就当练习了</address> <address>
</address> <address> </address> <address> USACO 2010 MARCH GOLD StarCowraft</address> <address> http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1829</address> <address> </address> <address> </address>
<address> </address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address>
接下来稍微弄了一下坐标旋转的问题，具体可以参考武汉大牛的博文http://dumbear.com/blog/?p=143
坐标旋转题目切得不多
<address> HDU 1700 Points on Cycle</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=1700</address> <address> 比较基础的一道题</address> <address> </address> <address> POJ 3845 Fractal</address> <address> http://poj.org/problem?id=3845</address> <address> 注意eps的取值</address> <address> </address> <address> POJ 1133 Stars</address> <address> http://poj.org/problem?id=1133</address> <address> </address> <address> Harbin Online Contest 2010</address> <address> http://acm.hrbeu.edu.cn/index.php?act=problem&id=1006&cid=16</address> <address> 三维坐标旋转。这个要有账号才能提交，还有就是Sample Input 中第二个Sample的“275”改成“270”</address> <address> </address> <address> HDU 3623 Covering Points (2010天津网络赛C题)</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=3623 (航电没有这题了)</address> <address> http://acm.tju.edu.cn/toj/showp3740.html </address> <address></address> <address> FZU 2002 Shade of Hallelujah Mountain (2010福州regional)</address> <address> http://acm.fzu.edu.cn/problem.php?pid=2002</address> <address>
HDU 4087 ALetter to Programmers (2011 北京现场赛)</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=4087</address> <address> 三维旋转矩阵 + 矩阵加速</address>
然后是旋转卡壳，一个很好的学习网站http://cgm.cs.mcgill.ca/~orm/rotcal.html（不过是英文的），后来找到一个大牛的blog里有部分翻译http://blog.csdn.net/ACMaker，综合起来看了一下，收益良多啊。
一些旋转卡壳的题目
POJ 2187 Beauty Contest
http://acm.pku.edu.cn/JudgeOnline/problem?id=2187
凸包求最远点对。可以暴力枚举，也可以使用旋转卡壳。
POJ 3608 Bridge Across Islands
http://acm.pku.edu.cn/JudgeOnline/problem?id=3608
两个凸包的最近距离。
上面两题可以参考blog：http://www.cppblog.com/staryjy/archive/2009/11/19/101412.html（上面代码很不错）
</address> <address> </address> <address> UVA 10173</address> <address> http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=13&problem=1114&mosmsg=Submission+received+with+ID+8029560</address> <address> 给定点集S,求S的最小覆盖矩形</address> <address> </address> <address> </address> <address> </address>
然后看了一些扫描线之类的东西。
推荐几道比不错的题目：
<address> POJ 2932 Coneology</address> <address> http://poj.org/problem?id=2932</address> <address> </address> <address> HDU 3124 Moonmist</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=3124</address> <address> 最近圆对问题（二分 + 扫描线）</address> <address></address> <address> HDU 3867 Light and Shadow</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=3867</address> <address> (按极角扫描)注意-PI和PI的位置分割</address>
下面看了一些随机算法：（08年顾研论文-《浅谈随机化思想在几何问题中的应用》）
（1）随机增量法：这个算法很犀利啊，把一些计算几何的问题降了一个n复杂度。（典型的有最小圆覆盖）
网上找了最小圆覆盖的随机增量算法，里面代码倒是不错，就是解释的不是很清楚，推荐看《计算几何算法与应用(第3版)》（邓俊辉译，清华大学出版社出版）中第91页“4.7最小包围圆”这个章节中的内容，比较详细也很清楚，代码我参考了这个blog的http://blog.csdn.net/pvpishard/archive/2011/01/27/6167262.aspx
（2）模拟退火：参考顾研论文
模拟退火的题目：
<address> POJ 1379 Run Away</address> <address> http://poj.org/problem?id=1379</address> <address> </address> <address> POJ 2420 A Star not a Tree?</address> <address> http://poj.org/problem?id=2420</address> <address> </address> <address> URAL 1520 Empire Strikes Back（推荐）</address> <address> http://acm.timus.ru/problem.aspx?space=1&num=1520</address> <address> 顾研论文例题，不错的题目</address> <address> </address> <address> POJ 2069 Super Star</address> <address> http://poj.org/problem?id=2069</address> <address> 此题我WA和TLE了很多次</address> <address> </address> <address> POJ 3301 Texas Trip</address> <address> http://poj.org/problem?id=3301</address> <address> 这题也可以用三分</address> <address> </address> <address> SPOJ 4409 Circle vs Triangle</address> <address> https://www.spoj.pl/problems/AREA1/</address> <address> 模拟退火 + 解析几何</address> <address> </address> <address> POJ 3285 Point of view in Flatland</address> <address> http://poj.org/problem?id=3285</address> <address> 这题的难点在于找到合适的评估函数，当然这题也可以通过解方程组来做</address> <address> </address> <address> POJ 2600 Geometrical dreams</address> <address> http://poj.org/problem?id=2600</address> <address> 这题不是模拟退火的题，但是可以用模拟退火过。非模拟退火的方法也不难</address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address>解析几何，平面最近点对，。。。这些搞得也不是很深入。
<address> </address> <address> </address>
折纸问题 参见大牛dumbear的blog http://dumbear.com/blog/?p=249
两道题目
<address> POJ 1921 Paper Cut</address> <address> http://poj.org/problem?id=1921</address> <address> 这题相对下一题还算比较好做</address> <address> </address> <address> POJ 3806 Origami Through-Hole</address> <address> http://poj.org/problem?id=3806</address> <address> 这题处理有点麻烦，我调试了很久才过</address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address> <address> </address>圆的面积并和交，详细可以看AekdyCoin大牛的blog
圆的面积并：http://hi.baidu.com/aekdycoin/blog/item/c1b28e3711246b3f0b55a95e.html
圆的面积交：http://hi.baidu.com/aekdycoin/blog/item/12267a4e9476153bafc3abbd.html
题目：
<address> SPOJ 8073 The area of the union of circles</address> <address> https://www.spoj.pl/problems/CIRU/</address> <address> </address> <address> SPOJ 3863 Area of circles</address> <address> https://www.spoj.pl/problems/VCIRCLES/</address> <address></address> <address> SPOJ 8119 CIRU2</address> <address> https://www.spoj.pl/problems/CIRUT/</address> <address> 圆面积并的拓展</address> <address> </address> <address> HDU 3467 Song of the Siren</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=3467</address> <address> </address> <address> HDU 3239 Jiajia's Robot (推荐)</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=3239</address> <address> 很巧妙的一道题，我是看了AC大牛blog中的留言才知道到方法的。</address> <address> 方法见AC大牛blog中的一条留言：http://hi.baidu.com/aekdycoin/blog/item/12267a4e9476153bafc3abbd.html</address> <address> </address> <address> </address> <address> </address> <address>
</address> <address>
</address> <address>
</address>
凸多边形的面积并
先看了AC大牛的blog学会了O(N^3)的方法，后来在做Codeforces的时候发现有O(N^2*logN)的方法，而且也不繁琐
AC大牛的博文：http://hi.baidu.com/aekdycoin/blog/item/fbe5a03232c71952ad4b5fcc.html
Codeforces Round #83 DIV1 的 E题用O(N^3)的方法过不掉第49组数据，然后研究了其他大牛的凸多边形交的代码
http://codeforces.com/contest/107/status/E
先是看了dagon的代码发现其实他的代码有问题，Codeforces的数据居然没有查出来。然后看了syntax_error的代码，
发现他是用类似梯形剖分的方法做的，复杂度O(N^2*logN)，果断就学习了
题目：http://codeforces.com/contest/107/problem/E
有关细节：http://www.cnblogs.com/ch3656468/archive/2011/10/17/2215551.html
<address></address> <address>
</address> <address> </address> <address>
</address> <address>
</address> <address> </address> <address> </address>
有一类题目是给出一些点，并告诉你哪些点之间有连线，并且这些连线段之间除端点之外没有其他交点（有时候这些线段是要自己处理出来的）。
然后题目要你求
1 每小块多边形的面积
2 有多少个K多边形内部不含点和线段
3 这些线段围成的图形的轮廓线
这类题目的方法都差不多，在很多大牛的blog里都可以找到类似的方法。
比如： gccfeli大牛的blog：http://gccfeli.cn/2007/09/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95-pku1092-%E5%A5%87%E7%89%B9%E7%9A%84%E6%8A%80%E5%B7%A7.html
watashi大牛的blog：http://watashi.ws/blog/970/andrew-stankevich-3-solution/
Isun大牛的blog：http://hi.baidu.com/xh176233756/blog/item/29652646f0e870006a63e5cb.html
题目：
<address> POJ 1092 Farmland</address> <address> http://poj.org/problem?id=1092</address> <address></address> <address> ZOJ 2361 Areas / SGU 209</address> <address> http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2361</address> <address> 不错的一题，watashi的blog里有解题报告</address> <address> </address> <address> POJ 3743 LL’s cake</address> <address> http://poj.org/problem?id=3743</address> <address> </address> <address> POJ 2164 Find the Border</address> <address> http://poj.org/problem?id=2164</address> <address>
</address> <address> </address> <address> </address> <address>
</address> <address>
</address> <address>
</address>
三维几何
网上有关三维几何的内容很少阿，代码和题目基本都不怎么能搜到，我也就切了不多的几题
前面坐标旋转里的两到题：
<address> Harbin Online Contest 2010</address> <address> http://acm.hrbeu.edu.cn/index.php?act=problem&id=1006&cid=16</address> <address> 三维坐标旋转。这个要有账号才能提交，还有就是Sample Input 中第二个Sample的“275”改成“270”</address> <address>
</address> <address> FZU 2002 Shade of Hallelujah Mountain (2010福州regional)</address> <address> http://acm.fzu.edu.cn/problem.php?pid=2002</address> <address> </address> <address>
SGU 110 Dungeon</address> <address> http://acm.sgu.ru/problem.php?contest=0&problem=110</address> <address> 三维光线反射</address> <address> </address> <address> FZU 1981 Three kingdoms (2010福州网络赛)</address> <address> http://acm.fzu.edu.cn/problem.php?pid=1981</address> <address> 坐标映射，我一开始用map一直TLE，只好改成不用map的代码 </address> <address> </address> <address> UVA 11275 3D Triangles</address> <address> http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2250</address> <address> HDU 4042是这题的加强版，我使用同样的代码AC的</address> <address> 对于这题题目中诡异的精度0.000001我并没有特别处理</address> <address> </address> <address> HDU 4042 Fireworks (2011北京网络赛)</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=4042</address> <address> 很不错的题目 (解题报告：http://hi.baidu.com/%D0%A1%CE%E4rj/blog/item/0114bb2dcd4cdef78b13991d.html)</address> <address> </address> <address> HDU 4087 ALetter to Programmers (2011 北京现场赛)</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=4087</address> <address> 三维旋转矩阵 + 矩阵加速</address>
<address>
</address> <address>
</address>
其他一些题目：
<address> EOJ 283 Target Practice</address> <address> http://202.120.106.94/onlinejudge/problemshow.php?pro_id=283</address> <address> 搜索 + 几何</address> <address> </address> <address> POJ 1688 Dolphin Pool</address> <address> http://poj.org/problem?id=1688</address> <address> 这题有好几种做法</address> <address> </address> <address> POJ 1981 Circle and Points</address> <address> http://poj.org/problem?id=1981</address> <address> 很经典的一道题目</address> <address> </address> <address> POJ 3675 Telescope</address> <address> http://poj.org/problem?id=3675</address> <address> 圆和多边形的公共面积</address> <address> </address> <address> POJ 1259 The Picnic</address> <address> http://poj.org/problem?id=1259</address> <address> 最大凸洞，计算几何 + DP</address> <address> </address> <address> POJ 1586 Three Sides Make a Triangle</address> <address> http://poj.org/problem?id=1586</address> <address> 题目内容很简单，方法也很明显，不过想AC可不容易，精度很恶心的一题，我是看了discuss才过的</address> <address> </address> <address> HDU 3629 Convex （推荐）</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=3629</address> <address> 一道不错的题目，这题有两种思路：</address> <address> 1)http://apps.topcoder.com/wiki/display/tc/TCO%2710+Online+Round+4</address> <address> 2)http://www.owent.net/2010/09/the-35th-acmicpc-asia-regional-tianjin-site-%E2%80%94%E2%80%94-online-contest-1009-convex-%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A.html</address> <address></address> <address> </address> <address> HDU 3644 A Chocolate Manufacturer's Problem (2010杭州网络赛)</address> <address> http://acm.hdu.edu.cn/showproblem.php?pid=3644</address> <address> 本来想用模拟退火水一下的，结果徘徊于WA和TLE之间无法AC</address> <address> </address> <address> FZU 1973 How many stars (推荐) (2010福州网络赛)</address> <address> http://acm.fzu.edu.cn/problem.php?pid=1973</address> <address> 比较经典的一道题目</address> <address> </address> <address> POI2007 对称轴osi</address> <address> http://www.zybbs.org/JudgeOnline/problem.php?id=1100</address> <address> 很犀利的一道题目，题意是判多边形的对称轴个数，原来做的这种题目都是用O(N^2)的复杂度来解的，</address> <address> 这次O(N^2)果断不行，加随机化也过不了，最后在解题报告的指导下才搞定这题。第一次发现计算几何</address> <address> 的问题居然还能用字符串的方法解。</address> <address> 网上搜到的解题报告：http://hi.baidu.com/nplusnplusnplu/blog/item/d260baef2e9e9c5879f055cb.html</address> <address> </address> <address> </address>
下次再搞计算几何的时候会更加深入一些。
京公网安备 11010502036488号