交通轨迹，想到一个暴力版，复杂度O（n^2） #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5+233; const double eps = 0.00000001; struct node { double x1; double y1; double x2; double y2; int id; int sum; }sa[N],sb[N]; struct node2 { double x; double y; }; node2 a,b,c,d; node2 aa,bb,cc,dd; bool judge(node s,node t) { a.x=s.x1; a.y=s.y1; b.x=s.x2; b.y=s.y2; c.x=t.x1; c.y=t.y1; d.x=t.x2; d.y=t.y2; if(min(a.x,b.x) <= max(c.x,d.x) && min(c.x,d.x) <= max(a.x,b.x) && min(a.y,b.y) <= max(c.y,d.y) &&min(c.y,d.y)<=max(a.y,b.y)) { double u,v,w,z;//保存叉乘 u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y); v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y); w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y); z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y); return (u*v<=eps && w*z<=eps); //浮点数判断大小 } return false; } int T,n,m; int main() { //freopen("in.txt","r",stdin); cin>>T; while(T--) { memset(sa,0,sizeof(sa)); cin>>n; int cnt=0; for(int i=1; i<=n; ++i) { char op; cin>>op; if(op=='T') { cnt++; // cout<<"cnt="<<cnt<<endl; cin>>sa[cnt].x1>>sa[cnt].y1>>sa[cnt].x2>>sa[cnt].y2; sa[cnt].id=cnt; sa[cnt].sum=0; } else { int q; cin>>q; //cout<<"cnt="<<cnt<<endl; for(int j=1; j<=cnt; ++j) { for(int k=j+1; k<=cnt; ++k) { if(judge(sa[j],sa[k])) { //cout<<"j="<<j<<" "<<"k="<<k<<endl; sa[j].sum++; sa[k].sum++; } } } //cout<<endl; cout<<sa[q].sum+1<<endl; } } cout<<endl; } return 0; }