暴力(判凸四边形) FZOJ 2148 Moon Game

题目传送门

题意：给了n个点的坐标，问能有几个凸四边形

分析：数据规模小，直接暴力枚举，每次四个点判断是否会是凹四边形，条件是有一个点在另外三个点的内部，那么问题转换成判断一个点d是否在三角形abc内

　　　　易得S (abd) + S (acd) + S (bcd) == S (abc)，求三角形面积

收获：比赛时没写出来，没想到用面积就轻松搞定，脑子有点乱，开始敲了计算几何点是否在凸多边形内的模板，WA了，整个人都不好了。收获就是要把计算几何的基础补上来

代码：

/************************************************
* Author        :Running_Time
* Created Time  :2015-8-23 13:40:19
* File Name     :H.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 33;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
const double PI = acos (-1.0);
struct Point	{
	double x, y;
};

int n;
Point pp[N];

double area(Point a, Point b, Point c)  {
    return fabs (0.5 * (a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - a.x * c.y - b.x * a.y));
}

bool cal(Point a, Point b, Point c, Point d)    {
    double sum = area (a, b, d) + area (a, c, d) + area (b, c, d);
    double tot = area (a, b, c);
    if (fabs (sum - tot) < EPS) return false;
    return true;
}

bool judge(Point a, Point b, Point c, Point d)  {
    if (!cal (a, b, c, d))   return false;
    if (!cal (a, b, d, c))   return false;
    if (!cal (a, d, c, b))   return false;
    if (!cal (d, b, c, a))   return false;
    return true;
}

int work(void)	{
	int ret = 0;
	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 l=k+1; l<=n; ++l)	{
					if (judge (pp[i], pp[j], pp[k], pp[l]))	ret++;
				}
			}
		}
	}

	return ret;
}

int main(void)    {
	int T, cas = 0;	scanf ("%d", &T);
	while (T--)	{
		scanf ("%d", &n);
		for (int i=1; i<=n; ++i)	{
			scanf ("%lf%lf", &pp[i].x, &pp[i].y);
		}
		printf ("Case %d: %d
", ++cas, work ());
	}

    return 0;
}