计算几何题目推荐

《计算几何题目推荐》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算几何题目推荐计算几何题目推荐计算几何题的特点与做题要领：1.大部分不会很难，少部分题目思路很巧妙2.做计算几何题目，模板很重要，模板必须高度可靠。3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。如果代码一片混乱，那么会严重影响做题正确率。4.注意精度控制。5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。因为整数不用考虑浮点误差，而且运算比浮点快。一。点，线，面，形基本关系，点积叉积的理解POJ2318TOYS（推荐）http://acm.pku.edu.cn/JudgeOnline/problem?id=231

2、8POJ2398ToyStorage（推荐）http://acm.pku.edu.cn/JudgeOnline/problem?id=2398一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。POJ3304Segmentshttp://acm.pku.edu.cn/JudgeOnline/problem?id=3304知识点：线段与直线相交，注意枚举时重合点的处理POJ1269IntersectingLineshttp://acm.pku.edu.cn/JudgeOnline/pro

3、blem?id=1269知识点：直线相交判断，求相交交点POJ1556TheDoors（推荐）http://acm.pku.edu.cn/JudgeOnline/problem?id=1556知识点：简单图论＋简单计算几何，先求线段相交，然后再用Dij求最短路。POJ2653Pick-upstickshttp://acm.pku.edu.cn/JudgeOnline/problem?id=2653知识点：还是线段相交判断POJ1066TreasureHunthttp://acm.pku.edu.cn/JudgeOnline/problem?id=1066知识点：线段相交判断，不

4、过必须先理解“走最少的门”是怎么一回事。POJ1410Intersectionhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1410知识点：线段与矩形相交。正确理解题意中相交的定义。详见：http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.htmlPOJ1696SpaceAnt（推荐）http://acm.pku.edu.cn/JudgeOnline/problem?id=1696德黑兰赛区的好题目。需要理解点积叉积的性质POJ3347KadjSquare

5、shttp://acm.pku.edu.cn/JudgeOnline/problem?id=3347本人的方法极度猥琐。复杂的线段相交问题。这个题目是计算几何的扩大数据运算的典型应用，扩大根号2倍之后就避免了小数。POJ2826AnEasyProblem?!（推荐）http://acm.pku.edu.cn/JudgeOnline/problem?id=2826问：两条直线组成一个图形，能容纳多少雨水。很不简单的EasyProblem，要考虑所有情况。你不看discuss看看能否AC。（本人基本不能）提示一下，水是从天空垂直落下的。POJ1039Pipehttp://acm.p

6、ku.edu.cn/JudgeOnline/problem?id=1039又是线段与直线相交的判断，再加上枚举的思想即可。POJ3449GeometricShapeshttp://acm.pku.edu.cn/JudgeOnline/problem?id=3449判断几何体是否相交，不过输入输出很恶心。此外，还有一个知识点，就是给出一个正方形（边不与轴平行）的两个对角线上的顶点，需要你求出另外两个点。必须掌握其方法。POJ1584ARoundPeginaGroundHolehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1584知识点：

7、点到直线距离，圆与多边形相交，多边形是否为凸POJ2074LineofSight（推荐）http://acm.pku.edu.cn/JudgeOnline/problem?id=2074与视线问题的解法，关键是求过两点的直线方程，以及直线与线段的交点。数据有一个trick，要小心。二。凸包问题POJ1113Wallhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1113知识点：赤裸裸的凸包问题，凸包周长加上圆周。POJ2007ScrambledPol