计算几何

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

题目链接 题意&思路： # 给出n个圆 求恰好k个圆相交的面积，k属于1..n 先放个别人的代码。 我真是体会到了软件工程这门课的重要性。 这代码真是烂得印象深刻。几何题全是面向过程？

题目链接 题意： # 求n个圆的面积并。 思路： # 发现和求2个圆的完全不一样，具体请参考 SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU）

hdu1724题目链接 题意： # 给定标准椭圆参数 \( a, b \) 以及两条竖直截面边界 \( x = l \) 与 \( x = r \)，求椭圆在 \( [l, r] \) 截面内的并集面积。 思路： # 辛普森积分学习笔记

16沈阳的阴影还在orz，来学习一下辛普森积分。 参考资料：梯形多步法和辛普森积分 辛普森计算定积分 辛普森积分是一种数值积分方法（然后现在只记得教计算方法的是一个小姐姐，并不记得当时学了什么orz 大概就是用二次抛物线近似计算曲边梯形面积，辛普森积分公式如下：

3680: 吊打XXX # Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 2043 Solved: 732 [Submit][Status][Discuss] Description # gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将 n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳 结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。 不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

hdu 5017 题目链接 题意：给出椭球方程的 6 个参数 a,b,c,d,e,f 问椭球上的点到原点 (0,0,0) 的最小距离是多少。 思路：感觉难点在于，如何保证搜到的点一直在椭球上。 一开始我考虑用椭球的参数方程，然后发现不记得是什么了 2333。

poj 1385 题目链接 题意：求多边形的重心。 思路： 抄模板（逃 嘛。。三角形的重心是三个点坐标的平均数。。。 多边形的重心其实就是先求三角形的重心然后再加权平均一下就好了。。。权值是面积比。

题目链接 题意：问一个小矩形能否放在一个大矩形中，给定两个矩形的尺寸。 思路：主要是斜着放比较难判断。学弟貌似写了离散化角度旋转。。。我的做法是。。直接考虑对角线。。。因为我认为对角线是最有可能放进去的位置。

1656: [Usaco2006 Jan] The Grove 树木 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 143 Solved: 88 [Submit][Status][Discuss] Description # The pasture contains a small, contiguous grove of trees that has no ‘holes’ in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She’s just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn’t think you could pass ’through’ the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here’s a typical example where ‘.’ is pasture (which Bessie may traverse), ‘X’ is the grove of trees, ‘’ represents Bessie’s start and end position, and ‘+’ marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): …+… ..+X+.. .+XXX+. ..+XXX+ ..+X..+ …+++ The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she’s starting ‘outside’ the grove instead of in a sort of ‘harbor’ that could complicate finding the best path.

题目链接 题意：给出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 题意：问圆和矩形是否相交 思路：主要特殊的包含情况，然后判断与线段相交。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月21日 星期一 21时38分22秒 4File Name :code/hdu/rr1221.cpp 5************************************************ */ 6 7#include <iostream> 8#include <string.h> 9#include <stdio.h> 10#include <algorithm> 11#include <cmath> 12#define eps 1e-8 13using namespace std; 14struct point 15{ 16 double x; 17 double y; 18}circle,a,b,c,d; 19double r; 20double dis(point &a,point &b) 21{ 22 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 23} 24 25bool ok() 26{ 27 28 if(dis(a,circle)<r && dis(b,circle) <r && dis(c,circle)<r && dis(d,circle) <r) 29 return false; 30 if(circle.x>=a.x && circle.x<=b.x) 31 { 32 if(fabs(circle.y-a.y) <= r || fabs(circle.y-b.y) <= r) 33 return true; 34 } 35 if((circle.y >= a.y && circle.y <=b.y) || (circle.y>=b.y && circle.y<=a.y)) 36 { 37 if(fabs(circle.x-a.x) <=r || fabs(circle.x-b.x) <=r) 38 return true; 39 } 40 if(dis(a,circle)<=r || dis(b,circle) <=r || dis(c,circle)<=r || dis(d,circle) <=r) 41 return true; 42 return false; 43} 44int main() 45{ 46 #ifndef ONLINE_JUDGE 47 freopen("code/in.txt","r",stdin); 48 #endif 49 int t; 50 scanf("%d",&t); 51 while(t--) 52 { 53 scanf("%lf %lf %lf %lf %lf %lf %lf",&circle.x,&circle.y,&r,&a.x,&a.y,&b.x,&b.y); 54 if(a.x > b.x) 55 swap(a,b); 56 c.x=a.x,c.y=b.y; 57 d.x=b.x,d.y=a.y; 58 59 if (ok()) 60 { 61 puts("YES"); 62 } 63 else 64 { 65 puts("NO"); 66 } 67 } 68 return 0; 69}

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) - …. We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such 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 ** Problem Description Given many points in a plane, two players are playing an interesting game. Player1 selects one point A as the vertex of an angle. Then player2 selects other two points B and C. A, B and C are different with each other. Now they get an angle B-A-C.

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. A transmitter T is located somewhere on a 1,000 square meter grid. It broadcasts in a semicircular area of radius r. The transmitter may be rotated any amount, but not moved. Given N points anywhere on the grid, compute the maximum number of points that can be simultaneously reached by the transmitter’s signal. Figure 1 shows the same data points with two different transmitter rotations.