交通轨迹,想到一个暴力版,复杂度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;
}