uvalive 7675 | 2016 北京 regional onsite H – A New Ground Heating Device (二分+多个圆面积并)

题目链接

题意:

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

思路:

训练[……]

Read more

SPOJ CIRUT – CIRU2 (多个圆交,求交任意次的面积,模板题)

题目链接

题意&思路:

给出n个圆

求恰好k个圆相交的面积,k属于1..n

 

先放个别人的代码。。。

我真是体会到了。。。软件工程这门课的重要性。。。

这代码真是烂得印象深刻。。。几何题全是面向过程?

circle和point 类写在一起。。。感觉所有糟糕的写法这[……]

Read more

spoj CIRU – The area of the union of circles (多个圆面积并,模板题)

题目链接

题意:

多n个圆的面积并。

思路:

发现和求2个圆的完全不一样,具体请参考

SPOJ 8073 The area of the union of circles(计算几何の圆并)(CIRU)

圆的面积并 

格林公式在面积并问题中的应用

(用格林公式搞真是跪烂了。。。。

没[……]

Read more

hdu 1724 Ellipse (辛普森积分模板题)

hdu1724题目链接

题意:

求图示区域的面积。

思路:

辛普森积分学习笔记

容易推出被积函数为  f(x)=bsqrt(1-(xx/a/a));

 

辛普森积分学习笔记

16沈阳的阴影还在orz,来学习一下辛普森积分。

参考资料:梯形多步法和辛普森积分

辛普森计算定积分

辛普森积分是一种数值积分方法(然后现在只记得教计算方法的是一个小姐姐,并不记得当时学了什么orz

大概就是用梯形近似计算曲边梯形面积,辛普森积分公式如下:

下面放代码:

[crayon[……]

Read more

hdu 5017 Ellipsoid (模拟退火,计算椭球到定点的最小距离)

 

hdu 5017 题目链接

题意:给出椭球方程的6的参数 a,b,c,d,e,f 

问椭球上的点到原点(0,0,,0)的最小距离是多少。

思路:感觉难点在于,如何保证搜到的点一直在椭球上。

一开始我考虑到了用椭球的参数方程。。。。然后发现不记得是什么了23[……]

Read more

poj 1380 Equipment Box (简单几何)

题目链接

题意:问一个小矩形能否放在一个大矩形中,给定两个矩形的尺寸。

思路:主要是斜着放比较难判断。学弟貌似写了离散化角度旋转。。。我的做法是。。直接考虑对角线。。。因为我认为对角线是最有可能放进去的位置。

&nbs[……]

Read more

codeforces #346 div 2 D. Bicycle Race (思维,计算几何,公式)

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

思路:搞了半天没搞出来qaq

 

From the track des[……]

Read more

bzoj 1610 [Usaco2008 Feb]Line连线游戏 (计算几何)

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

Read more

codeforces 14 C. Four Segments

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

第二步,检查两个方向的边是否各有两条。。

第三步,将[……]

Read more

hdu 1221 Rectangle and Circle

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