FZU 2148 Moon Game(幾何学問題)

タイトルリンク:FZU 2148 Moon Game
ジオメトリ.
凹四角形かどうかを判断します.
四角形に別の3つの点からなる三角形の内部に点がある場合、この四角形は凹四角形であり、そうでなければ凸四角形である.
凹四角形の内部のその点と残りの任意の2点は3つの三角形を構成することができて、この3つの三角形の面積の和はちょうど外部の3つの点からなる三角形の面積で、ここでこの問題を考えるとできます.
三角形の3つの点の2次元座標から三角形の面積を求める式はabs(p[a].x*p[b].y+p[c].x*p[a].y+p[b].x*p[c].y-p[c].x*p[b].y-p[a].x*p[c].y-p[a].x*p[c].y-p[b].x*p[a].y)*0.5である.

#include <iostream>
#include <cmath>
#include <stdio.h>

using namespace std;

const int MAX_N = 30 + 5;
const double e = 1e-7;

struct Point
{
    int x, y;
};
int T, n, cnt, num;
Point p[MAX_N];
double get_area(int a, int b, int c)
{
    return abs(p[a].x * p[b].y + p[c].x * p[a].y + p[b].x * p[c].y - p[c].x * p[b].y - p[a].x * p[c].y - p[b].x * p[a].y) * 0.5;
}
bool solve(int i, int j, int k, int m)
{
    double sum, a, b, c;
    sum = get_area(j, k, m);
    a = get_area(i, j, k);
    b = get_area(i, j, m);
    c = get_area(i, k, m);
    if(fabs(sum - a - b - c) < e)
        return false;
    sum = get_area(i, j, k);
    a = get_area(i, j, m);
    b = get_area(j, k, m);
    c = get_area(i, k, m);
    if(fabs(sum - a - b - c) < e)
        return false;
    sum = get_area(i, k, m);
    a = get_area(i, j, k);
    b = get_area(i, j, m);
    c = get_area(j, k, m);
    if(fabs(sum - a - b - c) < e)
        return false;
    sum = get_area(i, j, m);
    a = get_area(i, j, k);
    b = get_area(i, k, m);
    c = get_area(j, k, m);
    if(fabs(sum - a - b - c) < e)
        return false;
    return true;
}
int main()
{
    cin >> T;
    num = 0;
    while(T--)
    {
        cin >> n;
        cnt = 0;
        for(int i = 1; i <= n; i++)
            cin >> p[i].x >> p[i].y;
        for(int i = 1; i <= n; i++)
        {
            for(int j = i + 1; j<= n; j++)
            {
                for(int k = j + 1; k <= n; k++)
                {
                    for(int m = k + 1; m <= n; m++)
                    {
                        if(solve(i, j, k, m))
                            cnt++;
                    }
                }
            }
        }
        printf("Case %d: %d
", ++num, cnt);
    }
    return 0;
}