网站备案 太烦,北京的软件公司,怎么用wordpress写文章,做网站需要数据库么传送门 这个直接用并查集维护。 每加入一条线段就将它与其他能相交的集合合并#xff0c;维护一个sizesize域表示每个集合的大小。 代码#xff1a; #includebits/stdc.h
#define eps 1e-15
using namespace std;
int t,fa[1005],n,siz[1005],cnt;
struct pot{dou… 传送门 这个直接用并查集维护。 每加入一条线段就将它与其他能相交的集合合并维护一个sizesize域表示每个集合的大小。 代码 #includebits/stdc.h
#define eps 1e-15
using 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 xfa[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),cnt0;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 i1;icnt;i)if(check(l[i],l[cnt])){int fxfind(i);if(fxcnt)continue;fa[fx]cnt,siz[cnt]siz[fx];}}else{int k,fx;scanf(%d,k),printf(%d\n,siz[find(k)]);}}if(t)puts();}return 0;
} 转载于:https://www.cnblogs.com/ldxcaicai/p/9738401.html
