foj 计算几何(2007.7.23更新).txt

ACM-ICPC竞赛 计算几何 终极学习资料整理合集 包含多篇PPT

Hotter Colder
http://acm.fzu.edu.cn/problem.php?pid=1014
求线段的中位线，线段相交求交点，求凸多边形的面积，

无归之室
http://acm.fzu.edu.cn/problem.php?pid=1016
本题精度要求非常高，用三角函数的话，很容易就wa..

Reflections
http://acm.fzu.edu.cn/problem.php?pid=1035
求一条射线遇到圆后的反射光，
即圆和直线求交点，求点关于交点法线的对称点。

Pipe
http://acm.fzu.edu.cn/problem.php?pid=1088
求一条光线从管道口进入，最远能达到多远。
判断线段左右位置关系，求线段相交交点。

A Pilot in Danger!
http://acm.fzu.edu.cn/problem.php?pid=1120
判断点在区域内

Area in Triangle
http://acm.fzu.edu.cn/problem.php?pid=1195
在三角形内的气球膨胀，求膨胀后的面积。
分情况推公式

Triangle
http://acm.fzu.edu.cn/problem.php?pid=1302
在给定的n（ 1<=n<=50000）个点中，取3个点组成三角形，求面积最大。
显然这3个点在凸包上，点集凸包化+凸包上的点k^2(原来要k^3的，利用某些性质剪枝，降到k^2).

Area
http://acm.fzu.edu.cn/problem.php?pid=1329
Pick定理

Center of Gravity
http://acm.fzu.edu.cn/problem.php?pid=1330
已知半径，角度的扇形，求其重心到圆心的距离。

Stone
http://acm.fzu.edu.cn/problem.php?pid=1331
求多边形的重心

Surround the Trees
http://acm.fzu.edu.cn/problem.php?pid=1333
凸包

Star not a Tree?
http://acm.fzu.edu.cn/problem.php?pid=1355
费马点

Coplanar Points
http://acm.fzu.edu.cn/problem.php?pid=1393
利用差积判断4点共面。

长方形的并的面积
http://acm.fzu.edu.cn/problem.php?pid=1407
离散化

Common Area
http://acm.fzu.edu.cn/problem.php?pid=1472
三角形和圆的共同面积。

弹弓
http://acm.fzu.edu.cn/problem.php?pid=1482
n(1<=n<=700)个点中，最多有多少个点在同一条直线上。

牧场
http://acm.fzu.edu.cn/problem.php?pid=1485
n(2<=n<=100)个点中，取其中部分点组成的一个凸多边形，求这样的凸多边形的最大顶点数.

Oaiei's Trouble
http://acm.fzu.edu.cn/problem.php?pid=1510
图形学中的直线剪裁算法，可以用计算几何中的点和线段的关系，线段和线段的求交点来求解。





Defense the country
http://acm.fzu.edu.cn/problem.php?pid=1338

Treasure Hunt
http://acm.fzu.edu.cn/problem.php?pid=1332
线段相交

Minkowski Sum
http://acm.fzu.edu.cn/problem.php?pid=1379

Area Ratio
http://acm.fzu.edu.cn/problem.php?pid=1382
求三角形的内切圆，外接圆

Video Surveillance
http://acm.fzu.edu.cn/problem.php?pid=1032
简单题

最大可分离值问题
http://acm.fzu.edu.cn/problem.php?pid=1201