做了两天了,一直有问题,改了三个地方具体怎么回事我就不说了,只说一下对我改代码有帮助的几组数据:
8
0 0 1 0
3 0 3 1
4 0 4 1
5 0 6 0
4 0 5 0
3 0 4 0
2 0 3 0
1 0 2 0
(这些应该全CONNECTED,出NOT就错)

3
1 1 2 2 
3 3 4 4
0 0 1 0
(这些全NOT CONNECTED,注意#1 #2共线且不相交)

2
0 2 0 0
0 0 1 0 
(题里给的数据,共线相交,应该没问题吧)

我不会并查集,写后面那个地方那个难受啊,因为菜鸟,想先自己实现了再去学就会更好一点~~~小自吹一下.

最后是想啊,大家交流一下相交都是怎么判断的呗,先说自己的了:
比如比较#A和#B,先记下#A中点M
然后平移#A使其中点分别和#B的两端点重合，会得到#A两个新位置，记其端点分别为A1 A2 A3 A4
然后求四边形A1 A2 A3 A4面积S1，再求M与四点中的任两点组成的四个三角形的面积和S2，如果S1<S2，则不相交。
然后另个讨论共线不相交的情况。

• Re:终于做出来了,数据+感慨+讨论一起写一下 (41) 1107905594 2012-07-27 15:38:16