FZU 2148 Moon Game

URL: http://acm.fzu.edu.cn/problem.php?pid=2148

PS: 枚舉所以四個點的情況，判斷是為凸四邊形，判斷方法是求解一次凸包。

#include 
#include 
#include 
#include 
#include 
const int maxn  = 40;
using namespace std;

//Accepted	2148  GNU C++  656 ms	228KB	2154B	achiberx

struct point {
    int x, y;
    point(int a=0, int b=0):x(a), y(b){}
    int operator^(const point &op) const {
        return x*op.y - y*op.x;
    }
};

point p[maxn];
int n;
point tmp[8];
point p0;

int sqr(int x) {
    return x*x;
}

int dis2(point p0, point p1) {
    return sqr(p0.x-p1.x)+sqr(p0.y-p1.y);
}
point operator - (point A, point B) {
    return point(A.x-B.x, A.y-B.y);
}

int mul(point p0, point p1, point p2) {
    return (p1-p0)^(p2-p0);
}

bool cmp(point a, point b) {
    if(mul(p0, a, b)>0 || (mul(p0, a, b)==0 && dis2(p0, a)1 && mul(q[newn-1], q[newn-2], tmp[i])>=0)
            --newn;
        q[newn++] = tmp[i];
    }
    if(newn==4) return true;
    else return false;
}

int main()
{
    int T;
    int cnt = 0;
    scanf("%d", &T);
    for(int t = 1; t <= T; t++) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &p[i].x, &p[i].y);
        }
        cnt = 0;
        if(n<=3) {
            printf("Case %d: %d\n", t, cnt);
            continue;
        }
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                for(int k = j+1; k < n; k++) {
                    for(int q = k+1; q < n; q++) {
                        bool res = work(p[i], p[j], p[k], p[q]);
                        if(res) cnt++;
                    }
                }
            }
        }
        printf("Case %d: %d\n", t, cnt);
    }
    return 0;
}