题目大意：
在一个平面上有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 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <cmath> 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 ", (double) ans1 / 2 / C(3, n), (double) ans2 / C(3, n)); 58 } 59 #define ONLINE_JUDGE 60 int main(){ 61 #ifndef ONLINE_JUDGE 62 freopen("tri.in", "r", stdin); 63 freopen("tri.out", "w", stdout); 64 #endif 65 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_JUDGE 74 fclose(stdin); fclose(stdout); 75 #endif 76 return 0; 77 }