ACM计算几何题目总结及分类.doc

COJ /oj/prepare.do?fun=viewProblempid=1011 /oj/prepare.do?fun=viewProblempid=1024 /oj/prepare.do?fun=viewProblempid=1034 /oj/prepare.do?fun=viewProblempid=1035 /oj/prepare.do?fun=viewProblempid=1036 /oj/prepare.do?fun=viewProblempid=1037 /oj/prepare.do?fun=viewProblempid=1038 /oj/prepare.do?fun=viewProblempid=1078 /oj/prepare.do?fun=viewProblempid=1137 /oj/prepare.do?fun=viewProblempid=1172 /oj/prepare.do?fun=viewProblempid=1190 /oj/prepare.do?fun=viewProblempid=1211 /oj/prepare.do?fun=viewProblempid=1230 /oj/prepare.do?fun=viewProblempid=1231 /oj/prepare.do?fun=viewProblempid=1249 :8080/COJ/prepare.do?fun=viewProblempid=1257 :8080/COJ/prepare.do?fun=viewProblempid=1260 FOJ Hotter Colder /problem.php?pid=1014 求线段的中位线，线段相交求交点，求凸多边形的面积， 无归之室 /problem.php?pid=1016 本题精度要求非常高，用三角函数的话，很容易就wa.. Reflections /problem.php?pid=1035 求一条射线遇到圆后的反射光， 即圆和直线求交点，求点关于交点法线的对称点。 Pipe /problem.php?pid=1088 求一条光线从管道口进入，最远能达到多远。 判断线段左右位置关系，求线段相交交点。 A Pilot in Danger! /problem.php?pid=1120 判断点在区域内 Area in Triangle /problem.php?pid=1195 在三角形内的气球膨胀，求膨胀后的面积。 分情况推公式 Triangle /problem.php?pid=1302 在给定的n（ 1=n=50000）个点中，取3个点组成三角形，求面积最大。 显然这3个点在凸包上，点集凸包化+凸包上的点k^2(原来要k^3的，利用某些性质剪枝，降到k^2). Area /problem.php?pid=1329 Pick定理 Center of Gravity /problem.php?pid=1330 已知半径，角度的扇形，求其重心到圆心的距离。 Stone /problem.php?pid=1331 求多边形的重心 Surround the Trees /problem.php?pid=1333 凸包 Star not a Tree? /problem.php?pid=1355 费马点 Coplanar Points /problem.php?pid=1393 利用差积判断4点共面。 长方形的并的面积 /problem.php?pid=1407 离散化 Common Area /problem.php?pid=1472 三角形和圆的共同面积。 弹弓 /problem.php?pid=1482 n(1=n=700)个点中，最多有多少个点在同一条直线上。 牧场 /problem.php?pid=1485 n(2=n=100)个点中，取其中部分点组成的一个凸多边形，求这样的凸多边形的最大顶点数. Oaieis Trouble /problem.php?pid=1510 图形学中的直线剪裁算法，可以用计算几何中的点和线段的关系，线段和线段的求交点来求解。 Defense the country /problem.php?pid=1338 Treasure Hunt /problem.php?pid=1332 线段相交 Minkowski Sum /problem.php?pid=1379 Area Ratio /problem.php?pid=1382 求三角形的内切圆，外接圆 Video Surveillance /problem.php?pid=1032 简单题 最大可分离