【题意】抽象模型后转化为：给定n个直线，ans+=C(x,4)*8，x为每个经过直线数>=4的点的直线数，不存在平行直线。
【算法】数学
【题解】
运用了一个很简单的道理：经过同一个点的线段互相相交。
O(n^3)，枚举直线i和j相交，然后枚举后面直线判断是否过交点的条数x，将C(x,2)累加入答案。
O(n^2*log n)，只要O(n^2)跑一边交点(不去重)，排序，统计相同交点有几个就可以得知经过该交点的直线数了。
访问x次，则可由1+2+3+...+n-1=x求得n。
注意多关键字double排序。
注意eps=1e-6足矣。
#include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } /*------------------------------------------------------------*/ const int inf=0x3f3f3f3f,maxn=810,maxN=640100; const double eps=1e-6; struct cyc{double x,y;}anss[maxN]; int n,x1[maxn],x2[maxn],y1_[maxn],y2[maxn],tot; double k[maxn],b[maxn]; ll c[maxn],d[maxN]; void insert(double x,double y){anss[++tot].x=x;anss[tot].y=y;} bool cmp(cyc a,cyc b){return fabs(a.x-b.x)>eps?a.x<b.x:a.y<b.y;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ x1[i]=read(),y1_[i]=read(),x2[i]=read(),y2[i]=read(); if(x2[i]-x1[i])k[i]=1.0*(y2[i]-y1_[i])/(x2[i]-x1[i]); b[i]=1.0*y1_[i]-k[i]*x1[i]; } tot=0; for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ if(x2[i]-x1[i]==0){ if(x2[j]-x1[j]==0)continue; insert(x1[i],k[j]*x1[i]+b[j]); }else if(x2[j]-x1[j]==0){ insert(x1[j],k[i]*x1[j]+b[i]); }else{ double X=(b[i]-b[j])/(k[j]-k[i]); double Y=k[i]*X+b[i]; insert(X,Y); } } } sort(anss+1,anss+tot+1,cmp); c[4]=1; for(int i=5;i<=n;i++)c[i]=c[i-1]*i/(i-4); ll number=3; for(int i=4;i<=n;i++){number+=i-1;d[number]=i;} ll ans=0,num=0; anss[0].x=anss[0].y=-1; for(int i=1;i<=tot;i++)if(fabs(anss[i].x-anss[i-1].x)<eps&&fabs(anss[i].y-anss[i-1].y)<eps)num++;else{ ans+=c[d[num]];num=1; } ans+=c[d[num]]; printf("%lld",ans*8); return 0; }