第五个点数据无误
查看原帖
第五个点数据无误
592894
lantifac楼主2023/12/5 15:14

第五个点主要会错的地方是 Room #39:

100
24 -24
39 -27
23 -26
35 -28
22 -28
35 -34
22 -31
29 -36
21 -33
28 -39
20 -35
25 -41
19 -37
27 -48
17 -39
20 -44
15 -39
16 -45
13 -41
17 -55
11 -42
12 -53
8 -42
9 -59
6 -43
5 -47
4 -42
2 -55
1 -43
-1 -48
-1 -41
-6 -55
-3 -41
-4 -43
-5 -40
-8 -40
-6 -38
-9 -39
-9 -37
-15 -40
-10 -35
-17 -38
-11 -33
-24 -37
-12 -31
-23 -34
-12 -28
-20 -28
-14 -26
-28 -25
-14 -24
-28 -21
-14 -22
-22 -18
-12 -20
-17 -17
-12 -17
-15 -13
-12 -15
-15 -10
-10 -13
-19 -6
-8 -12
-13 -3
-6 -10
-12 -2
-5 -8
-9 0
-3 -7
-3 -5
-1 -7
-2 0
1 -5
1 4
4 -6
5 10
6 -6
8 8
9 -5
13 9
11 -7
15 0
13 -8
20 5
15 -8
21 -4
17 -9
20 -9
18 -12
32 -2
20 -13
27 -11
22 -15
29 -14
23 -17
26 -17
23 -19
36 -19
24 -22
27 -22

画出来图形大概是这样:

不妨拿出几条线交一下,发现 BC,DC,L1M1BC,DC,L_1M_1 交是蓝色区域,但它与 D1C1D_1C_1 交为空。

也就是说早就交空了,数据是正确的。

至于答案错误,是因为最后由于没有排除掉交为一个点或一条线的情况,导致剩下的直线大于两条。

解决方法:

如果加入一条无交的直线,那么之前所有交点都在它右侧,它会将队尾一直弹出直到只剩下队首,且队首与它转角必定 ≥π\ge \pi(否则它们总有交)

代码中,每当只剩下队首时,判断一下新加入直线与队首转角是否 ≥π\ge \pi,如果 ≥\ge 则无交。

2023/12/5 15:14
加载中...