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

题目链接

题意:

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

思路:

训练的时候一眼二分,但是求圆并的时候gg了。。毫无思路。

搞定了多个圆面积并。。这题就很easy了。。

需要注意,每次二分的时候,记得初始化圆的d…

 

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

题目链接

题意&思路:

给出n个圆

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

 

先放个别人的代码。。。

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

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

circle和point 类写在一起。。。感觉所有糟糕的写法这份代码全都占了。。。

打算改写一下。。。这代码实在是。。烂得看不下去了。。。

所以说。。。读别人代码。。。才能体会到代码风格的重要性啊。。。orz

重构了代码,感觉清爽了很多。。

 

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

题目链接

题意:

多n个圆的面积并。

思路:

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

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

圆的面积并 

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

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

没有仔细看细节,当成板子好了(我最菜.jpg

将代码写成了自己熟悉的风格。

以及双倍经验题:SPOJ VCIRCLES

 

 

 

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

hdu1724题目链接

题意:

求图示区域的面积。

思路:

辛普森积分学习笔记

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

 

辛普森积分学习笔记

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

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

辛普森计算定积分

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

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

下面放代码:

切了个练手题,慢慢补充总结。

需要注意的是,simpson对精度要求比较高。。。eps开到1E-10才过。。

hdu1724题目链接

hdu1724解题报告

所以问题就在于写出积分公式(如果是多重积分要变成累次积分?orz)

 

 

 

 

 

 

 

 

BZOJ 3680: 吊打XXX (广义费马点,模拟退火+爬山)

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足够矮所以不会掉到地上。

Input

输入第一行为一个正整数n(1<=n<=10000),表示gty的数目。
接下来n行,每行三个整数xi,yi,wi,表示第i个gty的横坐标,纵坐标和重力。
对于20%的数据,gty排列成一条直线。
对于50%的数据,1<=n<=1000。
对于100%的数据,1<=n<=10000,-100000<=xi,yi<=100000

Output

输出1行两个浮点数(保留到小数点后3位),表示最终x的横、纵坐标。

Sample Input

3
0 0 1
0 2 1
1 1 1

Sample Output

0.577 1.000

HINT

Source


By wangxz

思路:

看起来是物理题。。其实就是求广义非费马点。。

也就是带权费马点。

一般的费马点是说,所有点到这个点的距离之和最小。

带权的费马点就是每个点到这个点的距离*权值,和最小。

这道题用到的才是真正的模拟退火!

模拟退火很重要的一部分就是允许有一定概率向不优的方向走,之前写的所谓的“模拟退火”的题目,全都没有体现这一点。

所以那些,其实就是一个爬山法吧。。

而且看到主席如是说…

webwxgetmsgimg

 

 

这道题真的很棒。

初始搜索范围很大的时候用模拟退火,快速得到一个大致范围。

但是由于精度不能很好的保证,于是在做完模拟退火后在答案附近爬山。

完美的分段思想!

一直调不对样例的原因是。。。

忘记把ans初始化成最大值23333

 

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

 

hdu 5017 题目链接

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

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

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

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

然后看了题解,发现比较巧妙的做法是,只搜索x,y,然后从椭球方程中解出z。

x,y确定以后,椭球方程就变成了一个关于z的一元二次方程,可解。

由于是要求距离原点的最小距离,而现在可能得到的两个解是关于xoy平面对称的,只有z坐标不同,因此我们取距离原点近的那个z。

以及,感觉在平面上搜4个方向就好。。。没必要8个方向。。?

2016-08-31 14-49-34 的屏幕截图

wa到死是因为。。。计算距离。。忘记开根号。。。。。呵呵呵呵呵呵呵呵呵我是傻逼。。。

poj 1385 Lifting the Stone (多边形的重心)

poj 1385 题目链接

题意:求多边形的重心。

思路:

抄模板(逃

 

 

 

 

 

嘛。。三角形的重心是三个点坐标的平均数。。。

多边形的重心其实就是先求三角形的重心然后再加权平均一下就好了。。。权值是面积比。

 

poj 1380 Equipment Box (简单几何)

题目链接

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

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

 

BZOJ 1656: [Usaco2006 Jan] The Grove 树木(神奇的bfs之射线法)

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.

牧场里有一片树林,林子里没有坑.
    贝茜很想知道,最少需要多少步能围绕树林走一圈,最后回到起点.她能上下左右走,也能走对角线格子.牧场被分成R行C列(1≤R≤50,1≤C≤50).下面是一张样例的地图,其中“.”表示贝茜可以走的空地,  “X”表示树林,  “*”表示起点.而贝茜走的最近的路已经特别地用“+”表示出来.
 
题目保证,最短的路径一定可以找到.

Input

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).

    第1行输入R和C,接下来R行C列表示一张地图.地图中的符号如题干所述.

Output

* Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.

    输出最少的步数.

Sample Input

6 7
…….
…X…
..XXX..
…XXX.
…X…
……*

Sample Output

13
思路:我的思路是错的。。就不说了。。这题太神辣。。。用来求解绕过某一区域的最短路。。做法是找一个点做一条平行于边界的射线(单向)到另一边界。
射线法大概就是:如果和多变形交了奇数次,就说明在多边形内部,否则在外部。
讲真。。还不是特别明白。。。感觉和计算几何比较有关系。。。

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

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

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

 

From the track description follows that Maria moves the way that the water always located to the right from her, so she could fall into the water only while turning left. To check if the turn is to the left, let’s give every Maria’s moves directions a number: moving to the north — 0, moving to the west — 1, to the south — 2 and to the east — 3. Then the turn is to the left if and only if the number of direction after performing a turn dir is equal to the number before performing a turn oldDir plus one modulo 4.

This solution has complexity O(n).

 

以及还有一个O(1)的做法。。太神啦。。。

One can solve this problem in alternative way. Let the answer be equal to x (that means that the number of inner corners of 270 degrees equals x, but the number of inner corners of 90 degrees to n - x). As soon as the sum of the inner corners’ values of polygon of n vertices is equal to 180 × (n - 2), thenx × 270 + (n - x) × 90 equals to 180 × (n - 2). This leads us to , being the answer for the problem calculated in O(1).

 

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

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

妈蛋。。。。斜率不存在是横坐标相等啊,不是纵坐标啊。。。蠢哭了好么。。。。。。

 

妈蛋。。。。斜率不存在是横坐标相等啊,不是纵坐标啊。。。蠢哭了好么。。。。。。

 

 

选区_024

 

太他妈惨了。。。。

 

 

 
null

codeforces #339 div 2 C. Peter and Snow Blower

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