题目大意：
在一个平面上有N(N <= 1000)个点，其中任意三点不共线，求这些点组成的三角形的面积和每和三角形内部含的点数的个数和。
数据范围：
20%的数据 N <= 50, 30% N <= 100, 100% N <= 1000。
算法讨论
算法1：
看到这题还是有部分分的，那么我们首先映入脑袋中的就是O(N^4)的算法，暴力枚举三个点叉积算面积，然后再枚举剩下的点判断是否在当前的三角形内。
如何判断一个点在三角形内部，有个不错的教程：http://www.yalewoo.com/in_triangle_test.html
考场上打这个暴力还是30分妥妥的。
算法2：
O(N^2logn)。
首先对于第一问：
我们考虑，对于一条边来说，边外的点都能和其组成一个三角形，而在枚举边的过程中，可能会对一个三角形多次计算，所以为了避免这种重复计算，我们就要保证一定的顺序，做到不重不漏。于是，对于这样的散点图，我们经常用到的排序方法有两种，第一个是以x为第一关键字，以y为第二关键字进行排序，另一个就是极角排序。（至于不知道什么是极角的，自行百度）。
我们枚举每一个点让其做为一个边的起点，然后以这个点为基准进行极角排序（两种方法，一个是让其它点的坐标都减去这个点的坐标，然后atan2，另一个就是用这个点与其它点的斜率），下面给出这样一个过程。
我们看这样一张图，如果计算S（AOB） + S(AOC) + S(AOD)，那么这个面积和就等于 OA叉OB + OA叉OC ＋ OA叉OD
就等于 － ｘｂ ＊ ｙａ ＋ ｘａ ＊ ｙｂ － ｘｃ ＊ ｙａ ＋ ｘａ ＊ ｙｃ － ｘｄ ＊ ｙａ ＋ ｘａ ＊ ｙｄ ＝ －（ｘｂ ＋ ｘｃ ＋ ｘｄ） ＊ ｙａ ＋ ｘａ ＊ （ｙｃ ＋ ｙｄ ＋ ｙｂ），为了保证这个结合是成立的，我们必须保证上面计算的顺序，也要保证都是向左旋，这样叉积才是正的。所以我们对于每一个点为基准，然后枚举那个‘Ａ＇，就可以得到以每个点为端点的每一个三角形的面积。然后想办法减少计算的重复，就需要极角排序一下。
对于第二问，我们考虑，当我们每选定一个点的时候，那么它最多在Ｃ（２，ｎ－１）个三角形中，我们采用补集的思想，当且仅当三个点在这个点同侧的时候，这个点不在三个点围成的三角形中，那么，假设我们当前找的基准点是A，那么已经枚举的那个点是Ａ＇，我们只要统计ＡＡ＇一侧的点的数量就可以了，然后组合计数 Ｃ（２，．．．），计算得出答案。同样，为了避免重复， 我们要按照一定的顺序就ＯＫ了。
Codes：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 typedef long long ll; 9 10 int n;11 struct Point{12 double x, y, ji;13 14 Point(double _x = 0, double _y = 0): x(_x), y(_y) {}15 bool operator < (const Point &a) const{16 return ji < a.ji;17 }18 }p[1005 * 2], T[1005];19 20 int C(int x, int y){21 int ret = 1;22 for(int i = y; i > y-x; -- i){23 ret = ret * i;24 }25 for(int i = 1; i <= x; ++ i)26 ret = ret / i;27 return ret;28 }29 30 double Cross(Point a, Point b){31 return a.x * b.y - a.y * b.x;32 }33 34 void Solve(){35 ll ans1 = 0, ans2 = 0;36 for(int i = 1; i <= n; ++ i){37 int cnt = 0;38 for(int j = 1; j <= n; ++ j){39 if(j != i){40 ++ cnt;41 p[cnt].x = T[j].x - T[i].x; p[cnt].y = T[j].y - T[i].y;42 p[cnt].ji = atan2(p[cnt].y, p[cnt].x); 43 }44 }45 sort(p + 1, p + cnt + 1);46 for(int j = 1; j <= cnt; ++ j)47 p[cnt + j] = p[j];48 ans2 += C(3, cnt);49 for(int j = 1, k = 2; j <= cnt; ++ j){50 if(j == k) k ++;51 while(Cross(p[j], p[k]) > 0) k ++;52 Point tp(T[i].x + p[j].x, T[i].y + p[j].y);53 ans1 += (long long)Cross(T[i], tp) * (k - j - 1);54 ans2 -= (long long)(k - j - 1) * (k - j - 2) / 2;55 }56 }57 printf("%lf %lf\n", (double) ans1 / 2 / C(3, n), (double) ans2 / C(3, n));58 }59 #define ONLINE_JUDGE60 int main(){61 #ifndef ONLINE_JUDGE62 freopen("tri.in", "r", stdin);63 freopen("tri.out", "w", stdout);64 #endif65 66 scanf("%d", &n);67 for(int i = 1; i <= n; ++ i){68 scanf("%lf%lf", &T[i].x, &T[i].y);69 }70 71 Solve();72 73 #ifndef ONLINE_JUDGE74 fclose(stdin); fclose(stdout);75 #endif76 return 0;77 }