bzoj1132: [POI2008]Tro

求三角形面积，谁用海伦谁脑残谁用面积公式谁脑残咳咳

当然是叉积啦

然后枚举一个基准点

其他的点按照到这个点的斜率排序

维护一下后缀和即可

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;

struct node{LL x,y;}p[3100],t[3100],now;
bool cmp(node n1,node n2){return n1.x==n2.x?n1.y<n2.y:n1.x<n2.x;}
bool cmd(node n1,node n2){return n1.y*n2.x<n2.y*n1.x;}
LL sumx[3100],sumy[3100];
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp);
    
    LL ans=0;
    for(int i=1;i<=n;i++)
    {
        int tlen=0; now=p[i];
        for(int j=i+1;j<=n;j++)
            t[++tlen].x=p[j].x-p[i].x, t[tlen].y=p[j].y-p[i].y;
        sort(t+1,t+tlen+1,cmd);
        
        sumx[tlen+1]=0;sumy[tlen+1]=0;
        for(int j=tlen;j>=1;j--)
        {
            sumx[j]=sumx[j+1]+t[j].x;
            sumy[j]=sumy[j+1]+t[j].y;
            ans+=t[j].x*sumy[j+1]-t[j].y*sumx[j+1];
        }
    }
    printf("%lld.%lld
",ans/2,ans%2*5);
    return 0;
}