学步园

题目大意：也就是说，给你n个点，这n个点两两坐标不相同，任意三个点不在一条直线上，让你求出其中凸四边形的个数，n最大就30。

解题思路：

要想A这道题，必须知道几个最为基本的概念，也就是说，怎么判断一个四边形是不是凸四边形呢？我们知道，一个三边形，那么这个三边形一定是凸的，那么四边形，有可能存在样例中的情况。（0,0）（100,0）（0,100）（10,10）的情况，这样的话，得到的就是一个凹四边形了。

关于凸四边形的判断，我们知道下面这个结论就好了：

如果一个点在其余三个点构成的三角形的内部，那么这四个点构造的四边形就是我们说的凸四边形了，那么怎么判断这个点在不在这个三角形的内部呢？其实就用面积公式就好了~

S△bcd =  S△acd+S△abd+S△acb  <=> S△bcd - ( S△acd+S△abd+S△acb  )< eps

  const double eps = 1e-9;

知道了这个结论后，问题就只剩下怎么求解三角形的面积了，其实求解三角形的面积有很多种，我们最为常用的就是海伦公式了。

其实，我们还可以通过这个公式来求解，也就是说用三个点的坐标来搞，利用叉乘的性质，因为|a 叉乘 b| = 以a，b为边的平行四边形的面积，那么对这个面积除以2就是三角形的面积了

S = fabs(1.0*(a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y))/2

好了，关键的地方都说完了，剩下的就是按照题目的意思来切了~

代码：

# include<cstdio>
# include<iostream>
# include<cmath>

using namespace std;

# define MAX 50

const double eps = 1e-8;
int n;

struct node
{
    int x;
    int y;
}point[MAX];

double area ( struct node a,struct node b,struct node c )
{
    return fabs(1.0*(a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y))/2;
}

int check ( struct node a,struct node b,struct node c,struct node d )
{
    if ( fabs(area(b,c,d)-(area(a,b,c)+area(a,b,d)+area(a,c,d))) < eps)
        return 0;
    else
        return 1;
}

int main(void)
{
    int t;cin>>t;
    int icase = 0;
    while ( t-- )
    {
        cin>>n;
        icase++;
        int ans = 0;
        for ( int i = 0;i < n;i++ )
        {
            cin>>point[i].x>>point[i].y;
        }
        if ( n < 4 )
            printf("Case %d: %d\n",icase,ans);
            else
            {
                for ( int i = 0;i < n;i++ )
                {
                    for ( int j = i+1;j < n;j++ )
                    {
                        for ( int k = j+1;k < n;k++ )
                        {
                            for ( int l = k+1;l < n;l++ )
                            {
                                if ( check(point[i],point[j],point[k],point[l])&&check(point[j],point[k],point[l],point[i])
                                    &&check(point[k],point[l],point[i],point[j])&&check(point[l],point[i],point[j],point[k]) )
                                {
                                    ans++;
                                }
                            }
                        }
                    }
                }
                printf("Case %d: %d\n",icase,ans);
            }




    }



    return 0;
}