首页 > 代码库 > 【暴力+排除法】FZU 2148 Moon Game
【暴力+排除法】FZU 2148 Moon Game
比赛地址:点击打开链接
比赛做粗的4个题几乎都是水,感觉弱的水爆炸了。
这个题最初的思路是枚举找出四个点,做凸多边形的模板判断。C(30,4)。
结果答案不对。。后来发现模板上是要求点对的顺序是逆时针或顺时针输入。
于是用时钟排序的函数排序后判断:
bool cmp(point p1, point p2) { return atan2(p1.y, p1.x) < atan2(p2.y, p2.x); }
结果tle了两遍。。
最后发现其实不用模板上这样。可以用判断是不是凹多边形的办法,反正总体是可以确定的。
判断是否为凸四边形的方法是:如果4个点中存在某个点D,Sabd + Sacd + Sbcd = Sabc,那么不是凸四边形。
#include <stdlib.h>
#include <math.h>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAXN 1000
#define offset 10000
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
using namespace std;
class point
{
public:
int x,y;
int flag;
};
class line
{
public:
point a,b;
};
double xmult(point a,point b,point c)
{
return fabs((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x))/2;
}
bool is_convex(point a,point b,point c,point d)
{
if(fabs(xmult(b,c,d)-xmult(a,b,c)-xmult(a,c,d)-xmult(a,b,d))<eps)
return false;
return true;
}
/*
int is_convex(int n,point* p){
int i,s[3]={1,1,1};
for (i=0;i<n&&s[1]|s[2];i++)
s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
return s[1]|s[2];
}*/
bool cmp(point p1, point p2)
{
return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
}
int main()
{
point res[4];
point tar[31];
int testcase;
scanf("%d",&testcase);
for(int cnt=1;cnt<=testcase;cnt++)
{
int pointnum;
scanf("%d",&pointnum);
for(int i=0;i<pointnum;i++)
{
scanf("%d%d",&tar[i].x,&tar[i].y);
}
int h=0;
for(int a=1;a<=pointnum-3;a++)
{
for(int b=a+1;b<=pointnum-2;b++)
{
for(int c=b+1;c<=pointnum-1;c++)
{
for(int d=c+1;d<=pointnum;d++)
{
res[0].x=tar[a-1].x;
res[0].y=tar[a-1].y;
res[1].x=tar[b-1].x;
res[1].y=tar[b-1].y;
res[2].x=tar[c-1].x;
res[2].y=tar[c-1].y;
res[3].x=tar[d-1].x;
res[3].y=tar[d-1].y;
if(is_convex(res[0],res[1],res[2],res[3])&&is_convex(res[1],res[0],res[2],res[3])
&& is_convex(res[2],res[0],res[1],res[3]) && is_convex(res[3],res[0],res[1],res[2]))
h++;
}
}
}
}
printf("Case %d: %d\n",cnt,h);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。