Foj 2148 二维几何（点是否在三角形内）

题目大意：给n个坐标（不存在三点共线的点），求能够组成多少个凸四边形。

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

struct Point

{

    int x,y;

    Point(int x=,int y=):x(x),y(y){}

}p[];

typedef Point Vector;

Vector operator - (Vector A, Vector B){ return Vector(A.x-B.x,A.y-B.y);}

int AbsCross(Vector A,Vector B){ return fabs(A.x*B.y-A.y*B.x);}

Point read_point()

{

    Point p1;

    scanf("%d %d",&p1.x,&p1.y);

    return p1;

}

bool fun(int i,int j,int k,int m)

{

    int area1,area2,area3,area4,sum;

    area1=AbsCross(p[j]-p[i],p[k]-p[i]);

    area2=AbsCross(p[j]-p[i],p[m]-p[i]);

    area3=AbsCross(p[k]-p[i],p[m]-p[i]);

    area4=AbsCross(p[k]-p[j],p[m]-p[j]);

    sum=area2+area3+area4;

    if(sum!=area1) return true;

    return false;

}

bool is_ok(int i,int j,int k,int m)

{

    if(!fun(i,j,k,m)) return false;

    if(!fun(i,j,m,k)) return false;

    if(!fun(i,k,m,j)) return false;

    if(!fun(j,k,m,i)) return false;

    return true;

}

int main()

{

    int i,j,k,m,n,T,Icase,ans;

    scanf("%d",&T);

    for(Icase=;Icase<=T;Icase++)

    {

        ans=;

        scanf("%d",&n);

        for(i=;i<n;i++) p[i]=read_point();

        for(i=;i<n-;i++)

        {

            for(j=i+;j<n-;j++)

            {

                for(k=j+;k<n-;k++)

                {

                    for(m=k+;m<n;m++)

                    {

                        if(is_ok(i,j,k,m))

                            ans++;

                    }

                }

            }

        }

        printf("Case %d: %d\n",Icase,ans);

    }

    return ;

}