Codeforces

Luogu

分析

考虑三角形的面积公式：$S_{\triangle ABC}=\frac{1}{2}\left(\vec{OA}\times\vec{OB}+\vec{OB}\times\vec{OC}+\vec{OC}\times\vec{OA}\right)$，其中 $ABC$ 是逆时针顺序。

于是可以枚举一条直线 $l_i$，然后枚举另一条直线 $l_j$，计算它与之前枚举到的直线在 $l_i$ 上构成的边的贡献。

如果我们按斜率枚举 $l_j$，那么每次产生的边都是 $\vec{P_kQ}$，其中 $Q$ 是 $l_i$ 与 $l_j$ 的交点，$P_k$ 是 $l_j$ 之前的直线 $l_k$ 与 $l_i$ 的交点。

那么 $l_j$ 的贡献是 $\sum_k \vec{OP_k}\times\vec{OQ}$，也就是 $\left(\sum_k\vec{OP_k}\right)\times\vec{OQ}$。那么只要维护一下前面面的东西就好了。

最后要记得除以 $2$，还要除以 ${n\choose 3}$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10;
const double eps=1e-8;

struct Point {
    double x,y;
    Point(double x_=0,double y_=0): x(x_),y(y_) {}
};
typedef Point Vector;
Vector operator -(Vector a) { return Vector(-a.x,-a.y); }
Point operator +(Point a,Vector b) { return Point(a.x+b.x,a.y+b.y); }
Point operator -(Point a,Vector b) { return a+(-b); }
template<typename T>
Vector operator *(Vector a,T b) { return Vector(a.x*b,a.y*b); }
template<typename T>
Vector operator /(Vector a,T b) { return a*(1.0/b); }
double dot(Vector a,Vector b) { return a.x*b.x+a.y*b.y; }
double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

struct Line {
    Point x; Vector v;
    Line(Point x_=Point(0,0),Vector v_=Vector(0,0)): x(x_),v(v_) {}
};
bool cmp(Line a,Line b) {
    return atan2(a.v.y,a.v.x)+eps<atan2(b.v.y,b.v.x);
}

Point intersection(Line a,Line b) {
    Vector v=a.x-b.x;
    double t=cross(v,b.v)/cross(b.v,a.v);
    return a.x+a.v*t;
}

int n; Line l[N];

int main() {
    n=read();
    for (int i=1;i<=n;++i) {
        double a=read(),b=read(),c=read();
        if (!b) l[i]=Line(Point(c/a,0),Vector(0,1));
        else if (!a) l[i]=Line(Point(0,c/b),Vector(1,0));
        else l[i]=Line(Point(0,c/b),Vector(1,-a/b));
    }
    sort(l+1,l+n+1,cmp); double ans=0;
    for (int i=1;i<=n;++i) {
        Vector s(0,0);
        for (int j=i+1;j<=n;++j) {
            Point p=intersection(l[i],l[j]);
            ans+=cross(s,p),s=s+p;
        }
        for (int j=1;j<i;++j) {
            Point p=intersection(l[i],l[j]);
            ans+=cross(s,p),s=s+p;
        }
        debug("%.4lf\n",ans);
    }
    ans/=1.0*n*(n-1)*(n-2)/3;
    printf("%.5lf\n",ans);
    return 0;
}