fzu_2148

参考：https://blog.csdn.net/qq_32680617/article/details/51010533

题意：第一行给出T，接下来有T组数据，每组数据第一行给出N，接下来N行，每行输入一个点的x，y坐标。输出这些点一共可以构成多少凸四边形。
思路：凸包不好判断，但是凹包很好判断啊，假设如果四个点a，b，c，d，构成了凹包，且a点凹了进去，那a和另外三个点组成的三角形面积和一定等于b，c，d三个点构成的三角形面积。自己画个图就显而易见。
一个获取三角形面积的函数，加上一个判断四个三角形面积关系的函数，然后四层循环暴力枚举出所有可能。
思路很好想，就是细节处理上，要用fabs获取浮点数的绝对值，要用小于1e-6这种方式近似的判断作差结果是否为0，因为浮点数运算一般不会直接判定是否相等，因为涉及到精度，不准确，所以都是近似的判断是否相等。

#include <iostream>
#include <math.h>
using namespace std;
struct node{
    int x;
    int y;
};
node nodes[31];
double calculateS(node a,node b,node c)
{
    return fabs(1.0*(b.x-a.x)*(c.y-a.y)-1.0*(b.y-a.y)*(c.x-a.x))/2.0;
}
int is_tu(node a,node b,node c,node d)
{
    //判断d是不是凹点,是返回0
    //然后等下再调用的时候把四个顶点都判断一遍，全都不是凹点的话才是凸包，这样就不用一开始费力去找哪个是凹点了
    //注意此处要加绝对值不然凸包的时候会小于0的
    if(fabs(calculateS(a,b,c)-calculateS(b,c,d)-calculateS(a,c,d)-calculateS(a,b,d))<1e-6)
        return 0;
    return 1;
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;++i)
    {
        int sum=0;
        int n;
        cin>>n;
        for(int j=0;j<n;++j)
        {
            int x,y;cin>>x>>y;
            nodes[j].x=x;
            nodes[j].y=y;
        }
        for(int k=0;k<n;++k)
            for(int m=k+1;m<n;++m)
               for(int l=m+1;l<n;++l)
                  for(int h=l+1;h<n;++h){
                    if(is_tu(nodes[k],nodes[m],nodes[l],nodes[h])&&is_tu(nodes[k],nodes[m],nodes[h],nodes[l])
                       &&is_tu(nodes[k],nodes[l],nodes[h],nodes[m])&&is_tu(nodes[l],nodes[h],nodes[m],nodes[k]))
                       ++sum;
                  }
        cout<<"Case "<<i<<": "<<sum<<endl;
    }
    return 0;
}