计算几何

题目链接 题意： # 在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。

题目链接 题意&思路： # 给出n个圆

题目链接 题意： # 求n个圆的面积并。

hdu1724题目链接 题意： # 求图示区域的面积。

16沈阳的阴影还在orz，来学习一下辛普森积分。 参考资料：梯形多步法和辛普森积分 辛普森计算定积分 辛普森积分是一种数值积分方法（然后现在只记得教计算方法的是一个小姐姐，并不记得当时学了什么orz

3680: 吊打XXX # Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 2043 Solved: 732 [Submit][Status][Discuss]

hdu 5017 题目链接 题意：给出椭球方程的 6 个参数 a,b,c,d,e,f 问椭球上的点到原点 (0,0,0) 的最小距离是多少。

poj 1385 题目链接 题意：求多边形的重心。 思路： 抄模板（逃 嘛。。三角形的重心是三个点坐标的平均数。。。

题目链接 题意：问一个小矩形能否放在一个大矩形中，给定两个矩形的尺寸。

1656: [Usaco2006 Jan] The Grove 树木 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 143 Solved: 88 [Submit][Status][Discuss]

题目链接 题意：给出n+1个点，每次由i点到i+1点，每段线段之间保证不同向或者反向，第一个点和最后一个点保证重合。路径围成的封闭图形中间都是水，问有多少个危险点，使得如果在这个点忘记转弯就会掉进水里。

http://www.lydsy.com/JudgeOnline/problem.php?id=1610 题意：给出n个点，问有多少条直线，这些之间之间都不平行。 思路：求斜率（注意考虑斜率不存在），看有多少种斜率。 妈蛋。。。。斜率不存在是横坐标相等啊，不是纵坐标啊。。。蠢哭了好么。。。。。。

http://codeforces.com/contest/614/problem/C # 题意：给一个多边形和多边形外一定点，多边形绕定点旋转，问多边形扫过的面积。 思路：简单计算几何，找到多边形距离定点的最大和最小距离R和r，答案就是(R^2-R^2)*PI 需要注意的是：最大距离一定是从某点上取得，但是最小距离可能不在顶点上，而在某条边上。

http://codeforces.com/problemset/problem/14/C 题意：给出四条边的坐标，问能否形成一个边与坐标轴平行的矩形。边可能退化成点。 思路：首先第一步，检查有没有边退化成点以及是否有不平行的边。

http://acm.hdu.edu.cn/showproblem.php?pid=1221 题意：问圆和矩形是否相交 思路：主要特殊的包含情况，然后判断与线段相交。

C. A Problem about Polyline time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output There is a polyline going through points (0, 0) - (x, x) - (2_x_, 0) - (3_x_, x) - (4_x_, 0) - … - (2_kx_, 0) - (2_kx_ + x, x) - ….

Max Angle # **Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 678 Accepted Submission(s): 238 **

Transmitters Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 4817 Accepted: 2576 Description In a wireless network with multiple transmitters sending on the same frequencies, it is often a requirement that signals don’t overlap, or at least that they don’t conflict. One way of accomplishing this is to restrict a transmitter’s coverage area. This problem uses a shielded transmitter that only broadcasts in a semicircle.