高手请帮忙看看这两到数据结构的题目,急!!!
Data Structure & Algorithms:
Problem 1. Largest Slope
Design a data structure to maintain a dynamic set of points in the plane. The data structure should allow the operations INSERT, DELETE and MAX-SLOPE, where MAX-SLOPE return two points such that the line segment between them has maximum slope. What kind of data structure you are going to use? Also list max-slope algorithm using text descriptions or virtual codes and it's complexity using Big O.
Hint: A point is comprised by x and y coordinates.
Problem 2. Circle
Let S be a set of n points in the plane. Give an efficient algorithm that determines whether there exist four points in S that lie on the same circle. What kind of data structure you are going to use to store a set of points?
Also list your algorithm using text descriptions or virtual codes and it's complexity using Big O.
Hint. In general, three point uniquely determine a circle. If the 4th point has the same radii as three points do, it lies on the same circle.
Solution Sketch:
问题点数：0、回复次数：11Top
1 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-06-01 13:45:00 得分 0
markTop
2 楼foochow（无聊,灌水......）回复于 2005-06-01 14:00:01 得分 0
mark!!!Top
3 楼shine51151（美丽心情）回复于 2005-06-01 14:00:34 得分 0
不会 帮顶Top
4 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-06-01 14:01:17 得分 0
第一个就定义个简单的结构
strcut point
{
double x;
double y;
}
然后list<point>可以吗?这样INSERT, DELETE就ok,
斜率的问题,也是简单的数学公式吧.但是求最大,用什么算法好,没想好,学习.Top
5 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-06-01 14:04:46 得分 0
第2个类似组合算法吧,
是不是得 C(n,4)遍历一次,
Top
6 楼ryan_1223（乌鸦）回复于 2005-06-01 14:12:45 得分 0
可惜我英文烂啊~！要是中文的还可以看两眼。
路过~！！~！Top
7 楼swimmer2000（时间是用来浪费的,所以每当我做了一点事都觉得很自豪）回复于 2005-06-01 16:13:56 得分 0
upTop
8 楼swimmer2000（时间是用来浪费的,所以每当我做了一点事都觉得很自豪）回复于 2005-06-01 17:46:24 得分 0
upTop
9 楼wzjall（风）回复于 2005-06-01 21:54:49 得分 0
翻译如下,仅供参考.意译
第一题;设计一个可以管理动态集合的数据结构.该集合是点的集合(in the plane不是重点,不影响设计).
该数据结构中包含:插入,删除,max_slope(先求出任意两点构成的线段的斜率,然后求最大的斜率)
第二题;给出一个高效的算法:判断点集合中是否存在共圆的四点.
Top
10 楼mostideal（三甲）回复于 2005-06-02 00:14:49 得分 0
dingTop
11 楼zdy_8212（zdy_8212）回复于 2005-06-02 02:40:02 得分 0
1.用数学方式：在平面上设点，再求出斜率，算法就是要将点连成线。三角？
2。两个圆是否同心？半径上的点。
不好意思是那来的。？？Top
