x*********a
发帖数: 36 | 1 网上看的，说是F家的，哪位大侠说说怎么答？
Suppose we are given a set L of n line segments in the plane, where the
endpoints of each segment lie on the unit circle x^2 + y^2 = 1, and all 2n
endpoints are distinct. Describe and analyze an algorithm to compute the
largest subset of L in which no pair of segments intersects |
l*********8
发帖数: 4642 | 2 首先把(x,y)坐标转换成极坐标： (1, t), 1是半径，t是角度.
半径都一样，不用关心。每个点用一个角度t来表示就可以了。
每个线段就可以表示成(t1, t2), 让t1 < t2
given两个线段A(a1, a2)和B(b1,b2), a1
则A,B相交 当且仅当： b1
（到了这一步，比较容易判断两条线段是否相交了。但不相交的最大集合，还是没有太
好的算法。。。)
其实，如果把每条线段看成一个node。如果两条线段相交，则两个node之间有边。这样
就得到一个图G。
问题等同于寻找图G的最大独立集(maximum disjoint set), 这是一个np-hard问题。
【在 x*********a 的大作中提到】
: 网上看的，说是F家的，哪位大侠说说怎么答？
: Suppose we are given a set L of n line segments in the plane, where the
: endpoints of each segment lie on the unit circle x^2 + y^2 = 1, and all 2n
: endpoints are distinct. Describe and analyze an algorithm to compute the
: largest subset of L in which no pair of segments intersects
|
y****2
发帖数: 1017 | 3 dp O(n2)或者O(n3)都可以做
注意这道题，线段的2个端点都在单位圆上。 我们只要对端点排序。 然后，只要x1
dp[i][j] = max(1+dp[start+1][end-1] +dp[end+1][j]
for start in range(i+1, j) ) |
l*********8
发帖数: 4642 | 4 能不能举个例子讲详细点儿。
初始值是什么？ 计算的顺序是什么？
y1
【在 y****2 的大作中提到】
: dp O(n2)或者O(n3)都可以做
: 注意这道题，线段的2个端点都在单位圆上。 我们只要对端点排序。 然后，只要x1: : dp[i][j] = max(1+dp[start+1][end-1] +dp[end+1][j]
: for start in range(i+1, j) )
|
T*****u
发帖数: 7103 | |
d****n
发帖数: 233 | 6 可以这样，先算出N条线的斜率，排序找最大重复。Ｏ（ＮｌｏｇＮ)
【在 x*********a 的大作中提到】
: 网上看的，说是F家的，哪位大侠说说怎么答？
: Suppose we are given a set L of n line segments in the plane, where the
: endpoints of each segment lie on the unit circle x^2 + y^2 = 1, and all 2n
: endpoints are distinct. Describe and analyze an algorithm to compute the
: largest subset of L in which no pair of segments intersects
|
l*********8
发帖数: 4642 | 7 斜率不同也可以不相交
【在 d****n 的大作中提到】
: 可以这样，先算出N条线的斜率，排序找最大重复。Ｏ（ＮｌｏｇＮ)
|
z***e
发帖数: 58 | 8 LIS 问题，先按照min(p1,p2) 排序，where p1 p2表示线段端点的极坐标的那个角度。
然后就是就是经典的LIS问题了，dp[k] = max(dp[j] + 1) where j < k && seg[k].p2
> seg[j].p2 if seg[k].p1 and seg[j].p1 are selected to sort.复杂度O(n2) |
t*****l
发帖数: 241 | 9
The direction of your reduction is wrong...
【在 l*********8 的大作中提到】
: 首先把(x,y)坐标转换成极坐标： (1, t), 1是半径，t是角度.
: 半径都一样，不用关心。每个点用一个角度t来表示就可以了。
: 每个线段就可以表示成(t1, t2), 让t1 < t2
: given两个线段A(a1, a2)和B(b1,b2), a1: 则A,B相交 当且仅当： b1: （到了这一步，比较容易判断两条线段是否相交了。但不相交的最大集合，还是没有太
: 好的算法。。。)
: 其实，如果把每条线段看成一个node。如果两条线段相交，则两个node之间有边。这样
: 就得到一个图G。
: 问题等同于寻找图G的最大独立集(maximum disjoint set), 这是一个np-hard问题。
|
d****n
发帖数: 233 | 10 longway2008 was on right track at the beginning:
首先把(x,y)坐标转换成极坐标, 每个点用一个角度t来表示就可以了。每个线段就可
以表示成(t1, t2),
这样一来， 我们可以得到n个区间。将这些区间按t2排序,得到新的数组A。
问题变成从A中找最大的非重叠区间。
设F(i)为第１个区间到第ｉ个区间中的最大不重叠区间个数。
Ｆ（ｉ）＝ Ｍａｘ｛Ｆ（ｉ－１），１＋Ｆ（ｊ）｝，Ａ［ｊ］是１。。。ｉ－１
中结束点ｔ２最接近Ａ［ｉ］的起始点ｔ１并且不要Ａ［ｉ］重叠的区间。 ｊ可以采
用Ｂｉｎａｒｙｓｅａｒｃｈｄｅｄ。
简单ＤＰ， 时间复杂度Ｏ（ｎｌｏｇｎ）， 空间复杂度Ｏ（ｎ）。 |
|
|
l*********8
发帖数: 4642 | 11 我觉得问题不等同于“从A中找最大的非重叠区间”。
比如线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
看作两个区间的话，是重叠的。 但两条线段是不相交的。
【在 d****n 的大作中提到】
: longway2008 was on right track at the beginning:
: 首先把(x,y)坐标转换成极坐标, 每个点用一个角度t来表示就可以了。每个线段就可
: 以表示成(t1, t2),
: 这样一来， 我们可以得到n个区间。将这些区间按t2排序,得到新的数组A。
: 问题变成从A中找最大的非重叠区间。
: 设F(i)为第１个区间到第ｉ个区间中的最大不重叠区间个数。
: Ｆ（ｉ）＝ Ｍａｘ｛Ｆ（ｉ－１），１＋Ｆ（ｊ）｝，Ａ［ｊ］是１。。。ｉ－１
: 中结束点ｔ２最接近Ａ［ｉ］的起始点ｔ１并且不要Ａ［ｉ］重叠的区间。 ｊ可以采
: 用Ｂｉｎａｒｙｓｅａｒｃｈｄｅｄ。
: 简单ＤＰ， 时间复杂度Ｏ（ｎｌｏｇｎ）， 空间复杂度Ｏ（ｎ）。
|
l*********8
发帖数: 4642 | 12 如果线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
你的方法的答案包括几条线段？
p2
【在 z***e 的大作中提到】
: LIS 问题，先按照min(p1,p2) 排序，where p1 p2表示线段端点的极坐标的那个角度。
: 然后就是就是经典的LIS问题了，dp[k] = max(dp[j] + 1) where j < k && seg[k].p2
: > seg[j].p2 if seg[k].p1 and seg[j].p1 are selected to sort.复杂度O(n2)
|
d****n
发帖数: 233 | 13 注意这里区间是线段上两点的向心角，如果向心角相交，线段咋可能不相交？
【在 l*********8 的大作中提到】
: 我觉得问题不等同于“从A中找最大的非重叠区间”。
: 比如线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
: 看作两个区间的话，是重叠的。 但两条线段是不相交的。
|
h***s
发帖数: 45 | 14 我理解题意是："n条线段，所有线段的端点都在圆上，找出包含最多不相交线段的集合
。"
计算出所有线段的slope，有n个。
因为2n个点都是distinct的,所以n个线段不会有重叠的，找出不相交的线段最多的集合
，也就是找出同样斜率最多(平行线最多)的集合。如果将n个斜率排序，问题就转化成"
find the most duplicates in a sorted list"
Time: O(nlog(n) + n) --> TO(nlog(n))
Space: O(n) 需要一个array来存slopes，排序也会需要额外的空间，不会超过O(n)
不知道我理解的对不对，大家指正一下。 |
b******g
发帖数: 8 | 15 是否可以转化成计算最长递增子序列。两个线段A和B不相交的条件是A的左右端点都分
别在B的上方，将所有线段按左端点排序。
成"
【在 h***s 的大作中提到】
: 我理解题意是："n条线段，所有线段的端点都在圆上，找出包含最多不相交线段的集合
: 。"
: 计算出所有线段的slope，有n个。
: 因为2n个点都是distinct的,所以n个线段不会有重叠的，找出不相交的线段最多的集合
: ，也就是找出同样斜率最多(平行线最多)的集合。如果将n个斜率排序，问题就转化成"
: find the most duplicates in a sorted list"
: Time: O(nlog(n) + n) --> TO(nlog(n))
: Space: O(n) 需要一个array来存slopes，排序也会需要额外的空间，不会超过O(n)
: 不知道我理解的对不对，大家指正一下。
|
g*******g
发帖数: 50 | 16 (0, 180) 和(45，135)当然不相交啊
【在 d****n 的大作中提到】
: 注意这里区间是线段上两点的向心角，如果向心角相交，线段咋可能不相交？
|
z***e
发帖数: 58 | 17
Answer:
0
after sorting
(0.1,0.5) (0.2,0.3)
dp[0] = 0
dp[1] = 0 since endpoint 0: 0.5 larger than endpoint1 : 0.3
So it won't add 1.
【在 l*********8 的大作中提到】
: 如果线段A是(0.1, 0.5), 线段B是(0.2, 0.3)
: 你的方法的答案包括几条线段？
:
: p2
|
l*********8
发帖数: 4642 | 18 这两条线段是不相交的。 所以答案应该是两条线段，不是0条。
【在 z***e 的大作中提到】
:
: Answer:
: 0
: after sorting
: (0.1,0.5) (0.2,0.3)
: dp[0] = 0
: dp[1] = 0 since endpoint 0: 0.5 larger than endpoint1 : 0.3
: So it won't add 1.
|
d****n
发帖数: 233 | 19 这样看来相交可以定义为线段在X轴上的投影相交，并且在Ｙ轴上的投影也相交。
【在 g*******g 的大作中提到】
: (0, 180) 和(45，135)当然不相交啊
|
d****n
发帖数: 233 | 20 scratch, it's not right.
【在 d****n 的大作中提到】
: 这样看来相交可以定义为线段在X轴上的投影相交，并且在Ｙ轴上的投影也相交。
|
|
|
e********2
发帖数: 495 | 21 我们学校的DP练习题：对所有线段的2个端点分别排序，然后找两个排好续的最大公共
子序列LCS. O(N^2) |
e********2
发帖数: 495 | 22 这个是对的。LIS， LCS都行，LIS比LCS快。
【在 z***e 的大作中提到】
:
: Answer:
: 0
: after sorting
: (0.1,0.5) (0.2,0.3)
: dp[0] = 0
: dp[1] = 0 since endpoint 0: 0.5 larger than endpoint1 : 0.3
: So it won't add 1.
|
w*****t
发帖数: 485 | |
