这个直接用并查集维护。 每加入一条线段就将它与其他能相交的集合合并,维护一个sizesize域表示每个集合的大小。 代码:
#include#define eps 1e-15using namespace std;int t,fa[1005],n,siz[1005],cnt;struct pot{ double x,y;};struct line{pot a,b;}l[1005];inline int find(int x){ return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}inline pot operator-(pot a,pot b){ return (pot){a.x-b.x,a.y-b.y};}inline double cross(pot a,pot b){ return a.x*b.y-a.y*b.x;}inline bool check(line a,line b){ return (cross(a.a-b.a,a.b-b.a)*cross(a.a-b.b,a.b-b.b)<=eps)&&(cross(b.a-a.a,b.b-a.a)*cross(b.a-a.b,b.b-a.b)<=eps);}int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n),cnt=0; while(n--){ char op[3]; scanf("%s",op); if(op[0]=='P'){ ++cnt,fa[cnt]=cnt,siz[cnt]=1; scanf("%lf%lf%lf%lf",&l[cnt].a.x,&l[cnt].a.y,&l[cnt].b.x,&l[cnt].b.y); for(int i=1;i