?

Jack Straws

?

题目大意：给你一些塑料棒，散落在平面上，如果两个棒相交，那么这两个就是一堆的。假如1跟2相交，2跟3相交，1跟3不相交，那么1、2、3是一堆的，如果1跟3也相交，那么1、2、3更是一堆的了。

接下来有多个输入询问，输入两个塑料棒的编号，问这两个编号的塑料棒是不是一堆的（输入0 0时询问结束）。

?

解题思路：整体看上去是一个并查集的问题，因为只要是相交的就是一堆的，很明显的并查集。剩下的就是判断线段相交的问题了，注意线段共端点、共线都属于相交的范畴，不是个规范相交。

?

具体代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define sqr(x) ((x)*(x)) #define zero(x) (((x) > 0 ? (x) : (-x)) < eps) using namespace std; const double eps = 1e-8; struct Point { double x, y; } ; struct Line { Point a, b; } L[20]; double xmult(Point a, Point b, Point c) { return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x); } ///若共线，返回1;不共线，返回0。 int dot_inLine(Point p1, Point p2, Point p3){ return zero(xmult(p1, p2, p3)); } ///判两点在线段同侧,点在线段上返回0 int same_side(Point p1, Point p2, Line l){ return xmult(l.a, p1, l.b)*xmult(l.a, p2, l.b) > eps; } ///判点是否在线段上,包括端点 int dot_onLine_in(Point p, Line l){ return zero(xmult(p, l.a, l.b)) && (l.a.x-p.x)*(l.b.x-p.x) < eps && (l.a.y-p.y)*(l.b.y-p.y) < eps; } ///判两线段相交,包括端点和部分重合 int intersect_in(Line u, Line v){ if (!dot_inLine(u.a, u.b, v.a) || !dot_inLine(u.a, u.b, v.b)) return !same_side(u.a, u.b,v) && !same_side(v.a, v.b,u); return dot_onLine_in(u.a, v) || dot_onLine_in(u.b, v) || dot_onLine_in(v.a, u) || dot_onLine_in(v.b, u); } int f[100]; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } void unionSet(int x, int y) { x = find(x); y = find(y); if(x != y) { f[x] = y; } } int main() { int n; while(~scanf(%d, &n) && n) { for(int i = 1; i <= n; ++i) { f[i] = i; } for(int i = 1; i <= n; ++i) { scanf(%lf%lf%lf%lf, &L[i].a.x, &L[i].a.y, &L[i].b.x, &L[i].b.y); } int p, q; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(intersect_in(L[i], L[j])) { unionSet(i, j); } } } while(scanf(%d%d, &p, &q) && (p||q)){ if(find(q) == find(p)) { puts(CONNECTED); } else { puts(NOT CONNECTED); } } } return 0; } 
     
    
   
  

?