[CF 528E] Triangles 3000

作法：

我的作法和這篇講的第二個作法一樣，而實作的方法在那篇裡已經寫的很清楚了，這裡大概提一下他的證明。借用一下上面那篇裡面的圖，先無視掉$L_2$，我們關心的是在什麼時候「由$L_0,L_1,L_3$圍成的三角形」會被算成$-1$倍。首先注意到，對於任意四條直線$L_0,L_1,L_2,L_3$來說，如果現在要算$L_1,L_2,L_3$圍成的三角形面積，那麼他就是由其他3個三角形（$L_0,L_1,L_2$，$L_0,L_2,L_3$，$L_0,L_1,L_3$）的面積取兩個相加再扣掉另一個得來的，而扣掉的那個三角形一定會是「和$L_1,L_2,L_3$圍成的三角形有唯一的重合邊」的三角形，而滿足這件事的三角形也顯然是唯一的。因此回到無視掉$L_2$的圖，由上面的結論可以得到，如果有某一條$L_2$會使得在計算$L_1,L_2,L_3$圍成的三角形面積時，三角形$L_0,L_1,L_3$會被算成$-1$倍，那麼就代表三角形$L_1,L_2,L_3$必須和三角形$L_0,L_1,L_3$恰有一條邊重合。因此如果記$L_1,L_3$的交點為$P$，並且稱$P$把$L_1,L_3$分成了上下兩半部，那麼就可以推出$L_2$只能交$L_1$於上半部，交$L_3$於下半部，或是交$L_1$於下半部，交$L_3$於上半部。有了這件事之後就不難得到由$L_0$轉向$L_2$的夾角會介於$L_0$轉向$L_1$的夾角和$L_0$轉向$L_3$的夾角之間了。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=3000+10 ;
const DB eps=1e-7 ;
 
struct pt{DB x,y;};
pt operator - (const pt &a,const pt &b){return (pt){a.x-b.x,a.y-b.y};}
DB dot(const pt &a,const pt &b){return a.x*b.x+a.y*b.y;}
DB len(const pt &a){return sqrt(dot(a,a));}
DB cross(const pt &a,const pt &b){return a.x*b.y-a.y*b.x ;}
DB cross(const pt &a,const pt &b,const pt &c){return cross(b-a,c-a) ;}
 
struct line
{
    DB a,b,c,val;
    bool operator < (const line &rhs) const
    {
        return val>rhs.val ;
    }
    void scan(){scanf("%lf%lf%lf",&a,&b,&c);}
}L[maxn];
 
pt getinter(const line &P,const line &Q)
{
    DB d=cross((pt){P.a,Q.a},(pt){P.b,Q.b}) ;
    DB x=cross((pt){P.c,Q.c},(pt){P.b,Q.b}) ;
    DB y=cross((pt){P.a,Q.a},(pt){P.c,Q.c}) ;
    return (pt){x/d,y/d} ;
}
 
DB area(const pt &a,const pt &b,const pt &c)
{
    return fabs(cross(a,b,c))/2 ;
}
 
DB area(const line &P,const line &Q,const line &R)
{
    return area(getinter(P,Q),getinter(Q,R),getinter(P,R)) ;
}
 
DB getcos(const line &P,const line &Q)
{
    pt u=(pt){P.b,-P.a} , v=(pt){Q.b,-Q.a} ;
    if(cross(u,v)<-eps) v=(pt){-Q.b,Q.a} ;
    return dot(u,v)/len(u)/len(v) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++)
    {
        L[i].scan() ;
        if(i>1) L[i].val=getcos(L[1],L[i]) ;
    }
    sort(L+2,L+n+1) ;
    DB ans=0 ;
    for(int i=2;i<=n;i++) for(int j=i+1;j<=n;j++)
        ans+=area(L[1],L[i],L[j])*(n-2*(j-i))/n/(n-1) ;
    printf("%.10f\n",ans*6/(n-2)) ;
}