第二题用的dfs,代码好他妈长!!!
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
#include "stdlib.h"
#include<limits.h>
#include <iomanip>
#include<map>
#include <queue>
#include<set>
#include <sstream>
using namespace std;
typedef struct point
{
float x;
float y;
}Point;
bool lineIntersectSide(Point A, Point B, Point C, Point D)
{
float fC = (C.y - A.y) * (A.x - B.x) - (C.x - A.x) * (A.y - B.y);
float fD = (D.y - A.y) * (A.x - B.x) - (D.x - A.x) * (A.y - B.y);
if(fC * fD > 0){
return false;
}
return true;
}
bool sideIntersectSide(Point A, Point B, Point C, Point D)
{
if(!lineIntersectSide(A, B, C, D)) {
return false;
}
if(!lineIntersectSide(C, D, A, B)){
return false;
}
return true;
}
int query(int num,vector<vector<point> > qu){
queue <int > q;
int vis[qu.size()];
for(int i=0;i<qu.size();i++){
vis[i]=0;
}
int zu=1;
for(int t=0;t<qu.size();t++){
if(vis[t]==0){
vis[t]=zu;
q.push(t);
while(!q.empty()){
for(int i=0;i<qu.size();i++){
if(vis[i]==0){
bool t1=sideIntersectSide(qu[i][0],qu[i][1],qu[q.front()][0],qu[q.front()][1]);
if(t1){
q.push(i);
vis[i]=zu;
//cout<<i<<endl;
}
}
}
q.pop();
}
}
zu+=1;
}
int count=0;
num=vis[num-1];
for(int i=0;i<qu.size();i++){
if(vis[i]==num){
count++;
}
}
return count;
}
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<vector<point> > qu;
for(int i=0;i<n;i++){
char m;
cin>>m;
if(m=='T'){
float x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
point p1;
p1.x=x1;
p1.y=y1;
point p2;
p2.x=x2;
p2.y=y2;
vector<point > line;
line.push_back(p1);
line.push_back(p2);
qu.push_back(line);
}
if(m=='Q'){
int w;
cin>>w;
cout<<query(w,qu)<<endl;
}
}
}
}