bzoj 1132 [POI2008]Tro 几何

[POI2008]Tro

Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 1796 Solved: 604
[Submit][Status][Discuss]

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

HINT

枚举起点，然后求出以该点为起点的所有向量，然后求面积就可以了。

 #include<cstring>

 #include<cmath>

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #define N 3007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n;ll ans;

 struct Node

 {

     int x,y;

     friend inline ll operator*(Node x,Node y)

     {

         return x.x*y.y-x.y*y.x;

     }

     friend inline bool operator<(Node x,Node y)

     {

         if (x.y==y.y) return x.x<y.x;

         return x.y<y.y;

     }

 }a[N],b[N];

 bool cmp(Node x,Node y)

 {

     return x*y>;

 }

 void solve()

 {

     sort(a+,a+n+);

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

     {

         int tot=;ll sumx=,sumy=;

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

             b[++tot].x=a[j].x-a[i].x,

             b[tot].y=a[j].y-a[i].y;

         sort(b+,b+tot+,cmp);

         for (int j=;j<=tot;j++)

             sumx+=b[j].x,

             sumy+=b[j].y;

         for (int j=;j<=tot;j++)

         {

             sumx-=b[j].x;

             sumy-=b[j].y;

             ans+=(ll)b[j].x*sumy-b[j].y*sumx;

         }

     }

 }

 int main()

 {

     n=read();

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

         a[i].x=read(),a[i].y=read();

     solve();

     if (ans&) printf("%lld.5",ans/);

     else printf("%lld.0",ans/);

 }

 #undef ll

巴特西