FOJ 2148（求凸四边形数量）

题意：给n个点，求图中凸四边形的数量。

解法：n<=30,就暴力吧。n^4 ^_^。如果四个点构成一个凸四边形，那么任意一个点和其他三个点组成的三个三角形面积一定大于其余三个点组成的三角形面积大。

代码：

#include 
#include 
using namespace std;
struct point
{int x,y;
} points[40];
int abs(int k){if(k<0) return -k;return k;}
int mult(point a,point b,point c)
{a.x-=c.x;a.y-=c.y;b.x-=c.x;b.y-=c.y;return abs(a.x*b.y-a.y*b.x);
}
bool OK(point a,point b,point c,point d)
{if(mult(a,b,c)+mult(a,c,d)+mult(a,b,d)<=mult(b,c,d))return false;if(mult(b,a,c)+mult(b,c,d)+mult(b,a,d)<=mult(a,c,d))return false;if(mult(c,a,b)+mult(c,b,d)+mult(c,a,d)&l

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！