题解 P3476 【[POI2008]TRO-Triangles】

FZzzz · 2019-09-07 14:18:40 · 题解

似乎其他两篇题解都说得不太清楚的样子，那我写一篇好懂一点的吧。

首先使用assert，测出n\le3000。

我们考虑三个点A，B，C组成的三角形面积，根据叉积的几何意义可知S_{\triangle ABC}=\frac{|(x_B-x_A)(y_C-y_A)-(x_C-x_A)(y_B-y_A)|}{2}，整理得S_{\triangle ABC}=\frac{|x_A(y_B-y_C)+y_A(x_C-x_B)+x_By_C-x_Cy_B|}{2}。

那我们为了不暴力统计，考虑依次固定一个点，比如A点。

但这就产生一个问题：如果其他点相对A的极角跨度超过180^\circ的话，绝对值无法消去，不好处理。所以我们将所有点按照纵坐标从小到大排序，然后依次考虑。每次考虑时，把后面所有点复制一下，按照极角再排一次序。这样只要C排在B后面，绝对值就可以去掉。

然后我们依次考虑所有点作为点B。可以发现只要知道后面所有点的坐标之和，就能一次算出所有三角形面积和。所以我们从后往前扫描B点，维护后缀和即可。

总时间复杂度为n^2\log n。代码如下：

#include<iostream>
#include<algorithm>
#include<cctype>
#include<cstdio>
using namespace std;
typedef long long ll;
inline ll readint(){
    ll x=0;
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
struct Point{
    ll x,y;
    Point(int x=0,int y=0):x(x),y(y){}
};
typedef Point Vector;
inline Point readpoint(){
    Point p;
    p.x=readint();
    p.y=readint();
    return p;
}
Vector operator -(Vector a,Vector b){
    return Vector(a.x-b.x,a.y-b.y);
}
inline ll cross(Vector a,Vector b){
    return a.x*b.y-b.x*a.y;
}
int n;
const int maxn=3000+5;
Point p[maxn];
bool cmp1(Point a,Point b){
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
Point p2[maxn];
Point aa;
bool cmp2(Point a,Point b){
    return cross(a-aa,b-aa)>0;
}
ll ans=0;
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    for(int i=0;i<n;i++) p[i]=readpoint();
    sort(p,p+n,cmp1);
    for(int i=0;i<n;i++){
        aa=p[i];
        for(int j=i+1;j<n;j++) p2[j]=p[j];
        sort(p2+i+1,p2+n,cmp2);
        ll sx=0,sy=0;
        for(int j=n-1;j>i;j--){
            ans+=aa.x*(p2[j].y*(n-j-1)-sy)+aa.y*(sx-p2[j].x*(n-j-1))+p2[j].x*sy-sx*p2[j].y;
            sx+=p2[j].x;
            sy+=p2[j].y;
        }
    }
    if(ans%2==1) cout<<ans/2<<".5"<<endl;
    else cout<<ans/2<<".0"<<endl;
    return 0;
}