您正在查看 "计算几何" 分类下的文章 2011/08/26 14:13 【题目地址】
http://poj.org/problem?id=1912
【题目大意】
给定一个点集 (<=10^5)， 然后给出若干询问(<=10^5)，每个询问是一条直线，问所有的点是否在这个直线的同一侧
【解题思路】
本题可以把点集都看成一个凸包。 然后问题转化为 看一个直线是否和给定的凸包相交
【暴力做法】
每次扫描凸包的边，判交， 每个查询复杂度 O(N)
【旋转卡(qia/ka)壳(qiao/ke)】
如果给定的 |
2010/12/17 18:48 
我们在初中就学习过叉乘， 在上图中， 2个橙色向量的叉乘的绝对值为粉色阴影部分面积的2倍。 而我们知道叉乘是有正有负的，如果按照上图的顺序叉乘出来那么结果应该是 大于0的，相反下图叉乘的结果则是小于0 (右手定则) |
2010/12/08 21:44 2010/10/12 13:51 【题目地址】
http://acm.timus.ru/problem.aspx?space=1&num=1775
【题目大意】
给出N 个直径为 1.0的钉子， 现在假设你可以在任意一个点丢出一个直径为 r的球，这个球滚过的地方所有的钉子一律消失 (哪怕是擦边而过)， 求最小的直径， 使得球至少可以使 K 个钉子消失！
【解题思路】
======================= 我是纯洁的分割线==========================
(... 刚看完题)
: 这题太BT了，果断不做！ |
2010/09/04 23:24 2010/08/27 22:25 POJ
1039 光线在管道中对多射多远。黑书例题，枚举关键点。
1066 正方形区域中有n条线段，求从边界到某点最少穿过几条线段。黑书练习题。可B |
2010/08/26 19:31 【问题求解】
给定N 个圆形，求出其并集.
【算法分析】
PS.以下算法基于正方向为 逆时针
考虑上图中的蓝色圆,绿色的圆和蓝色的圆交于 A,B 2个交点 ,我们在逆时针系下考虑，那么 可以知道 对于蓝色的圆，它对应的某个 角度区间被覆盖了
假设 |
2010/08/09 23:25 【问题求解】
给定N 个圆形，求出其交集.
【算法分析】
考虑上图中的蓝色圆,绿色的圆和蓝色的圆交于 A,B 2个交点 ,我们在逆时针系下考虑，那么 可以知道 对于蓝色的圆，它对应的某个 角度区间被覆盖了
假设 区间为 [A, B], 并且角度是按照 圆心到交点的 向量的 极角来定义 (为了方便，我一般都把角度转化到 [0,2pi]区间内) 那么可 |
2010/07/22 10:02 2010/06/22 10:33 题目描述：
给平面上N个点的坐标Xi、Yi，其中|Xi|<2000，|Yi|<2000。给出圆的半径R，求R能覆盖的最多的点的个数。
题目分析：
最初的分析就是移动，保证点在圆周上，然后圆以这一点为轴转动360度，检查有多少个点能被圆覆盖。操作时，对于基点i，如果dist(i, j)<D那么就以i点为轴转动圆周到j在圆周上。但是这么做的正确性没有仔细想过，但是实现起来就相当麻烦了。时间复杂度上是O(N^2)肯定是可以接受的。这种想法还有待于更深入的讨论。
|
2010/06/11 8:50 2010/05/25 19:52 2010/05/16 19:22 【E: Map】
枚举题意，最终可以发现题目所要描述的意思
既找到缩略图中一点，使得坐标和原来的城市重合
由以上公式不难得到O(1)算法
|
2010/04/18 13:25 2010/03/07 14:36 | | |
