FZU2148 Moon Game

给你一些点，让你找出不同的凸四边形的个数，一开始可能想到的是凸包，后来发现n只有30，所以可以暴力枚举，那怎么样来判断是一个凸四边形呢，只要排除凹四边形就可以了， 对于一个凹四边形，总存在一个点d，跟另外三个点a,b,c, 满足这样一个关系 Sabd+Sacd+Sbcd = Sabc,自己画图可以发现的，暴力枚举四个点，四个点中若任意找出一个 满足这个式子，那么它就不是凸四边形了，就排除，若都不满足这个式子，那么就算找到一个

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

#define inf 0xfffffff
//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

//#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin)  
//#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) 




//
//void TestArray() 
//{
//    char chs[] = {‘a‘, ‘d‘, ‘c‘, ‘e‘, ‘b‘};
//    int count = sizeof(chs)/sizeof(char);
//    
//    next_permutation(chs+0, chs + count);
//    
//    printf("TestArray:\n");
//    for(int i = 0; i < count; i++) {
//            printf("%c\t", chs[i]);
//    }
//    
//    printf("\n");
//}
//
//void TestVector()
//{
//     char chs[] = {‘a‘, ‘d‘, ‘c‘, ‘e‘, ‘b‘};
//     int count = sizeof(chs)/sizeof(char);
//     vector<char> vChs(chs, chs + count);
//     
//     next_permutation(vChs.begin(), vChs.end());
//     
//     printf("TestVector:\n");
//     vector<char>::iterator itr;
//     for(itr = vChs.begin(); itr != vChs.end(); itr++) {
//             printf("%c\t", *itr);
//     }
//     printf("\n");
//}
//
//int main(int argc, char *argv[])
//{
//    TestArray();
//    printf("\n");
//    TestVector();
//    
//    system("PAUSE");
//
//	return EXIT_SUCCESS;
//}

typedef struct Node {
	int x,y;
};

Node node[50];

void clear() {
	memset(node,0,sizeof(node));
}

double cals(Node a,Node b,Node c) {
	return a.x*b.y + a.y*c.x + b.x*c.y - (c.x*b.y + a.x*c.y + b.x*a.y);
}

int detal(Node a,Node b,Node c,Node d) {
	double sum1 = fabs(cals(a,b,d)) + fabs(cals(a,c,d)) + fabs(cals(b,c,d));
	double sum2 = fabs(cals(a,b,c));
	if(fabs(sum1 - sum2) <= eps) return 1;
	return 0;
}

int cal(Node a,Node b,Node c,Node d) {
	if(detal(a,b,c,d))return 0;
	if(detal(a,b,d,c))return 0;
	if(detal(a,c,d,b))return 0;
	if(detal(b,c,d,a))return 0;
	return 1;
}


int main() {
	int  t,Case  = 0;
	int n;
	scanf("%d",&t);
	while(t--) {
		clear();
		scanf("%d",&n);
		for(int i=0;i<n;i++) 
			scanf("%d %d",&node[i].x,&node[i].y);
		int ans = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n,j!=i;j++) {
				for(int k=0;k,n,k!=i,k!=j;k++) {
					for(int l=0;l<n,l!=i,l!=j,l!=k;l++) {
						if(cal(node[i],node[j],node[k],node[l]))
							ans++;
					}
				}
			}
		}
		printf("Case %d: %d\n",++Case,ans);
	}
	return EXIT_SUCCESS;
}

FZU2148 Moon Game

原文：http://blog.csdn.net/yitiaodacaidog/article/details/19765789