fzu Problem 2148 Moon Game（几何 凸四多边形 叉积）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 const double eps = 1e-8;  //定义成double类型
 9 
10 struct point
11 {
12     int x, y;
13 } p[50];
14 double area(point a, point b, point c)
15 {
16     return (fabs((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))/2);   //一定要fabs(),有可能为负的，
17 }
18 bool ok(point a, point b, point c, point d)
19 {
20     if(fabs(area(b,c,d)-area(a,b,c)-area(a,c,d)-area(a,b,d)) < eps)
21         return false;
22     return true;
23 }
24 int main()
25 {
26     int t, i, j, n, k, ans, a, b;
27     scanf("%d", &t);
28     for(k = 1; k <= t; k++)
29     {
30         ans = 0;
31         scanf("%d", &n);
32         for(i = 0; i < n; i++)
33             scanf("%d%d", &p[i].x, &p[i].y);
34 
35         if(n<4)
36            printf("Case %d: %d", k, ans);
37         else
38         {
39             for(i = 0; i < n; i++)
40                 for(j = i+1; j < n; j++)
41                     for(a = j+1; a < n; a++)
42                         for(b = a+1; b < n; b++)
43                             if(ok(p[i],p[j],p[a],p[b])&&ok(p[j],p[i],p[a],p[b])
44                                &&ok(p[a],p[i],p[j],p[b])&&ok(p[b],p[i],p[j],p[a]))
45                                 {
46                                     ans++;
47                                 }
48             printf("Case %d: %d\n", k, ans);
49         }
50     }
51     return 0;
52 }