この問題はテンプレートで十分です。エンドポイントにリンクされる線はないため、ちょうど 3 本の線が同じ点で交差する場合はありません。
/\*
\* GCA : "コンピュータは絶対的に人工的な主題であり、数学は神である"
\*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#else
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 100005
#define PB push\_back
#define oo INT\_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
struct point {
double x, y;
};
struct line {
point a, b;
};
#define zero(x) (((x)>0?(x):-(x))<eps)
double xmult(point p1, point p2, point p0) {
return (p1.x - p0.x) \* (p2.y - p0.y) - (p2.x - p0.x) \* (p1.y - p0.y);
}
double xmult(double x1, double y1, double x2, double y2, double x0, double y0) {
return (x1 - x0) \* (y2 - y0) - (x2 - x0) \* (y1 - y0);
}
int same\_side(point p1, point p2, line l) {
return xmult(l.a, p1, l.b) \* xmult(l.a, p2, l.b) > eps;
}
int same\_side(point p1, point p2, point l1, point l2) {
return xmult(l1, p1, l2) \* xmult(l1, p2, l2) > eps;
}
int opposite\_side(point p1, point p2, line l) {
return xmult(l.a, p1, l.b) \* xmult(l.a, p2, l.b) < -eps;
}
int opposite\_side(point p1, point p2, point l1, point l2) {
return xmult(l1, p1, l2) \* xmult(l1, p2, l2) < -eps;
}
int dots\_inline(point p1, point p2, point p3) {
return zero(xmult(p1, p2, p3));
}
int dots\_inline(double x1, double y1, double x2, double y2, double x3,
double y3) {
return zero(xmult(x1, y1, x2, y2, x3, y3));
}
//点が線分上にあるかどうかを判断する、端点を含む
int dot\_online\_in(point p, line l) {
return zero(xmult(p, l.a, l.b)) && (l.a.x - p.x) \* (l.b.x - p.x) < eps
&& (l.a.y - p.y) \* (l.b.y - p.y) < eps;
}
int dot\_online\_in(point p, point l1, point l2) {
return zero(xmult(p, l1, l2)) && (l1.x - p.x) \* (l2.x - p.x) < eps
&& (l1.y - p.y) \* (l2.y - p.y) < eps;
}
int intersect\_in(line u, line v) {
if (!dots\_inline(u.a, u.b, v.a) || !dots\_inline(u.a, u.b, v.b))
return !same\_side(u.a, u.b, v) && !same\_side(v.a, v.b, u);
return dot\_online\_in(u.a, v) || dot\_online\_in(u.b, v)
|| dot\_online\_in(v.a, u) || dot\_online\_in(v.b, u);
}
int intersect\_in(point u1, point u2, point v1, point v2) {
if (!dots\_inline(u1, u2, v1) || !dots\_inline(u1, u2, v2))
return !same\_side(u1, u2, v1, v2) && !same\_side(v1, v2, u1, u2);
return dot\_online\_in(u1, v1, v2) || dot\_online\_in(u2, v1, v2)
|| dot\_online\_in(v1, u1, u2) || dot\_online\_in(v2, u1, u2);
}
int intersect\_ex(line u, line v) {
return opposite\_side(u.a, u.b, v) && opposite\_side(v.a, v.b, u);
}
int intersect\_ex(point u1, point u2, point v1, point v2) {
return opposite\_side(u1, u2, v1, v2) && opposite\_side(v1, v2, u1, u2);
}
int n;
line lines\[M\];
int real\[M\];
int main() {
ios\_base::sync\_with\_stdio(0);
int test;
scanf("%d",&test);
while(test--){
int realnum=0;
Set(real,0);
scanf("%d",&n);
double ux,uy,vx,vy;
for(int i=0;i<n;i++){
scanf("%lf%lf%lf%lf",&ux,&uy,&vx,&vy);
lines\[i\].a.x=ux;
lines\[i\].a.y=uy;
lines\[i\].b.x=vx;
lines\[i\].b.y=vy;
}
int ans=0;
for(int i=0;i<n;i++){
int now=1;
for(int j=0;j<n;j++){
if(i==j)continue;
if(intersect\_ex(lines\[i\],lines\[j\])){
now++;
}
}
ans+=now;
}
printf("%d\\n",ans);
if(test)Pln();
}
}