题目描述：给你n个点（4~700）， 问你能够成多少个不同的凸四边形。

解题报告：

暴力的话C(700,4)必然超时，发现，任何一个凹包必然是其中一点在其它3点构成的三角形内。

然后就考虑，能不能求出所有凹包的个数，然后用总数C(n, 4)减去凹包的个数，就是答案。

依次枚举每个点i，看看其它点能够成多少个包括点i的三角形，就是以这个点为中心的凹包的个数。

找三角形也要一定的技巧，也是通过逆向思维：找出有多少个三角形不包括点i，然后用总三角形个数C(n – 1, 3) – 这个个数就是就是以这个点为中心的凹包的个数。

注意到，如果3个点不能圈住中心点，则必然是存在一条通过中心点的直线，使得这三个点都在直线的同侧。利用这个形式，我们用如下方法寻找三角形：

1：以中心点为中心，对剩余n-1个点极角排序。

2：依次处理排序后的n-1个点，对于每一个点i，依次往后扫描，找到第一个点j，是j和i的夹角大于180度。

3：那么点i + 1到点j – 1的所有点都可以和点i构成不包括中心点的三角形。个数是

C(j – i – 1, 2)

具体算法如图：

 

http://s8/middle/64675f5449022a7b2aa87&6903629 计算几何 2010天津网络预赛 计算技巧" TITLE="HDU 3629 计算几何 2010天津网络预赛 计算技巧" />

注意到：如果每次找j点都从i点出发的话，那么算法就成了N³的复杂度了。其实每次的j点都是从上个j点之后开始的，降低一维复杂度。

 

         自己以前没有注意到的代码技巧：

         计算极角时，如果是负数（-pi ~ 0），就把它加上2 * pi，这样就把角度统一到了0~2pi。

另外，向这题顺次统计两个点的夹角时，由于会出现转了一圈的情况不好计算角度，所以在原来数组后面再顺次加上n-1一个点，角度同一加2pi，

for(int j = 0; j < n - 1; j++) ans[j + n - 1] = ans[j] + 2 * pi;

这样计算角度直接减就好了。

代码如下：

#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

struct pint{double x, y;}jeo[1000];

double ans[2000];

#define eps 1e-8

long long C(int a, int b)

{

    long long aa = a, bb = b, ans = 1;

    for(int i = 0; i < b; i++) ans *= (aa - i);

    for(int i = 2; i <= b; i++) ans /= i;

    return ans;

}

int t, n;

int main()

{

    double pi = acos(-1.0);

    scanf("%d", &t);

    while(t--)

    {

        long long re = 0;

        scanf("%d", &n);

        for(int i = 0; i < n; i++) scanf("%lf%lf", &jeo[i].x, &jeo[i].y);

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

        {

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

            {

                if (j == i) continue;

                double tmp = atan2(jeo[j].y - jeo[i].y, jeo[j].x - jeo[i].x);

                if (tmp <= -eps) tmp += 2 * pi;

                j < i ? ans[j] = tmp : ans[j - 1] = tmp;

            }

            sort(ans, ans + n - 1);

            int k = 1;

            long long re2 = 0;

            for(int j = 0; j < n - 1; j++) ans[j + n - 1] = ans[j] + 2 * pi;

            for(int j = 0; j < n - 1; j++)

            {

                while(fabs(ans[k] - ans[j]) - pi < 0) k++;

                if (k - j - 1 >= 2) re2 += C(k - j - 1, 2);

            }

            re += C(n - 1, 3) - re2;

        }

        printf("%I64d\n", C(n, 4) - re);

    }

    return 0;

}