CF528E Triangles 3000

luogu

既然要求三角形面积,不如考虑三角形的面积公式.因为是三条直线,所以可以考虑利用三个交点来算面积,如果这个三角形按照逆时针方向有\(ABC\)三点,那么他的面积为\(\frac{\vec{OA}*\vec{OB}+\vec{OB}*\vec{OC}+\vec{OC}*\vec{OA}}{2}\),其实也就是一个大三角形减去两个小三角形,得到的就是要求的三角形

所以可以先枚举一条直线,注意到三角形面积是可以枚举算贡献的,所以只要求出所有在这条直线上的边的贡献就行了.把这条直线当做\(x\)轴,对于剩下的直线,按照逆时针方向枚举(先按斜率排序然后从当前直线循环枚举一圈),加入的直线产生交点,然后这个新交点\(B\)会和之前的交点产生\(\sum_A\vec{OA}*\vec{OB}\)的贡献.显然向量叉积的和可以改为和的叉积,所以维护前缀和即可

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<vector>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#include<set>

#define LL long long

#define db double

using namespace std;

const int N=3000+10;

const db eps=1e-6;

int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

struct point

{

    db x,y;

    point(){}

    point(db nx,db ny){x=nx,y=ny;}

    point operator + (const point &bb) const {return point(x+bb.x,y+bb.y);}

    db operator * (const point &bb) const {return x*bb.y-y*bb.x;}

}pr;

struct line

{

    db a,b,c;

    bool operator < (const line &bb) const {return -(a/b)<-(bb.a/bb.b);}

}a[N],az;

point jiao(line aa,line bb){return point((bb.b*aa.c-aa.b*bb.c)/(bb.b*aa.a-aa.b*bb.a),(bb.a*aa.c-aa.a*bb.c)/(bb.a*aa.b-aa.a*bb.b));}

db sm;

int n;

int main()

{

    //qwqwq

    n=rd();

    for(int i=1;i<=n;++i)

    {

        a[i].a=rd(),a[i].b=rd(),a[i].c=rd();

        if(!a[i].b) az=a[i],--n,--i;

    }

    sort(a+1,a+n+1);

    if(az.a) a[++n]=az;

    for(int i=1;i<=n;++i)

    {

        pr.x=pr.y=0;

        for(int j=i+1;j<=n;++j)

        {

            point nw=jiao(a[i],a[j]);

            sm+=pr*nw,pr=pr+nw;

        }

        for(int j=1;j<i;++j)

        {

            point nw=jiao(a[i],a[j]);

            sm+=pr*nw,pr=pr+nw;

        }

    }

    db xx=(db)n*(db)(n-1)*(db)(n-2)/6;

    printf("%.8lf\n",sm/2/xx);

    return 0;

}

巴特西

CF528E Triangles 3000

最新文章

热门文章