Description

平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和 N<=3000

Input

第一行给出数字N,N在[3,3000] 下面N行给出N个点的坐标,其值在[0,10000]

Output

保留一位小数,误差不超过0.1

Sample Input

5

0 0

1 2

0 2

1 0

1 1

Sample Output

7.0

Solution

\(ans=\frac{1}{2}\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=j+1}^n|(y_j-y_i)(x_k-x_i)-(y_k-y_i)(x_j-x_i)|\)

枚举第一个点，求出其它点的相对坐标

然后为了去绝对值，让所有点按计较排序，保证叉积是正的

\(ans_i=\frac{1}{2}\sum_{j=i+1}^n\sum_{k=j+1}^ny_j*x_k-y_k*x_j\)

\(~~~~~~~~~=\frac{1}{2}(\sum_{j=i+1}^ny_j\sum_{k=j+1}^nx_k-\sum_{j=i+1}^nx_j\sum_{k=j+1}^ny_k)\)

对最后的 \(\sum\) 做前缀和就好了

#include
    
     #define ui unsigned int#define ll long long#define db double#define ld long double#define ull unsigned long long#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)const int MAXN=3000+10;int n,cnt;ld ans;struct point{    int x,y;    inline bool operator < (const point &A) const {        return y
     
      A.k;    };};cross cs[MAXN];template
      
        inline void read(T &x){    T data=0,w=1;    char ch=0;    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();    if(ch=='-')w=-1,ch=getchar();    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();    x=data*w;}template
       
         inline void write(T x,char ch='\0'){    if(x<0)putchar('-'),x=-x;    if(x>9)write(x/10);    putchar(x%10+'0');    if(ch!='\0')putchar(ch);}template
        
          inline void chkmin(T &x,T y){x=(y
         
          
            inline void chkmax(T &x,T y){x=(y>x?y:x);}template
           
             inline T min(T x,T y){return x
            
             
               inline T max(T x,T y){return x>y?x:y;}int main(){ read(n); REP(i,1,n)read(pt[i].x),read(pt[i].y); std::sort(pt+1,pt+n+1); REP(i,3,n) { REP(j,1,i-1)cs[j]=(cross){pt[i].x-pt[j].x,pt[i].y-pt[j].y,atan2((ld)(pt[i].x-pt[j].x),(ld)(pt[i].y-pt[j].y))}; std::sort(cs+1,cs+i);ld sx=0,sy=0; REP(j,1,i-1) { if(j!=1)ans+=sx*(ld)cs[j].y-(ld)cs[j].x*sy; sx+=(ld)cs[j].x,sy+=(ld)cs[j].y; } } printf("%.1Lf\n",ans/2); return 0;}