题目链接：fzu 2148 Moon Game
题目大意：给出n个点，判断可以组成多少个凸四边形。
解题思路：因为n很小，所以直接暴力，判断是否为凸四边形的方法是：如果4个点中存在某个点D，Sabd + Sacd + Sbcd = Sabc,则说明是凹四边形。
#include#include #include const int N = 50; struct point { int x, y; void get() { scanf("%d%d", &x, &y); } }p[N]; int n; void init() { scanf("%d", &n); for (int i = 0; i < n; i++) { p[i].get(); } } double area(point a, point b, point c) { return 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 OK(point a, point b, point c, point d) { double sum = fabs(area(a, b, d)) + fabs(area(a, c, d)) + fabs(area(b, c, d)); double tmp = fabs(area(a, b, c)); if (fabs(sum - tmp) < 1e-9) return true; return false; } bool judge(point a, point b, point c, point d) { if (OK(a, b, c, d)) return false; if (OK(a, b, d, c)) return false; if (OK(a, c, d, b)) return false; if (OK(b, c, d, a)) return false; return true; } int solve() { int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int x = j + 1; x < n; x++) { for (int y = x + 1; y < n; y++) { if (judge(p[i], p[j], p[x], p[y])) ans++; } } } } return ans; } int main () { int cas; scanf("%d", &cas); for (int i = 1; i <= cas; i++) { init(); printf("Case %d: %d\n", i, solve()); } return 0; }