落絮飞雁的个人网站

顺流而下,把梦做完

HDOJ2108:Shape of HDU

Problem Description
话说上回讲到海东集团推选老总的事情,最终的结果是XHD以微弱优势当选,从此以后,“徐队”的称呼逐渐被“徐总”所取代,海东集团(HDU)也算是名副其实了。
创业是需要地盘的,HDU向钱江肉丝高新技术开发区申请一块用地,很快得到了批复,据说这是因为他们公司研发的“海东牌”老鼠药科技含量很高,预期将占全球一半以上的市场。政府划拨的这块用地是一个多边形,为了描述它,我们用逆时针方向的顶点序列来表示,我们很想了解这块地的基本情况,现在请你编程判断HDU的用地是凸多边形还是凹多边形呢?

 

Input
输入包含多组测试数据,每组数据占2行,首先一行是一个整数n,表示多边形顶点的个数,然后一行是2×n个整数,表示逆时针顺序的n个顶点的坐标(xi,yi),n为0的时候结束输入。

 

Output
对于每个测试实例,如果地块的形状为凸多边形,请输出“convex”,否则输出”concave”,每个实例的输出占一行。

 

Sample Input
4
0 0 1 0 1 1 0 1
0

 

Sample Output
convex

 

采用的方法是三角函数求内角度数,判断角是否超过180.

问题:

sqrt函数中形参必须为double,但double不能用^2进行乘方,降低了代码可读性。

忘记判断最后一点与初始两点的角度。

还是WA:

#include
#include
#include
int main()
{
	int  flag,n,ni;
	double a, b, c,cc,arc;
	double num[2][10000];
	while(~scanf("%d", &n)&&n!=0)
	{
		memset(num, 0, sizeof(num));
		flag = 0;
		for (ni = 0; ni < n; ni++)
		{
			scanf("%lf%lf", &num[0][ni], &num[1][ni]);
		}
		for (ni = 2; ni < n; ni++)
		{
			a = sqrt((num[0][ni - 2] - num[0][ni - 1])*(num[0][ni - 2] - num[0][ni - 1]) + (num[1][ni - 2] - num[1][ni - 1])*(num[1][ni - 2] - num[1][ni - 1]));
			b = sqrt((num[0][ni - 1] - num[0][ni])*(num[0][ni - 1] - num[0][ni]) + (num[1][ni - 1] - num[1][ni])*(num[1][ni - 1] - num[1][ni]));
			c = sqrt((num[0][ni - 2] - num[0][ni])*(num[0][ni - 2] - num[0][ni]) + (num[1][ni - 2] - num[1][ni])*(num[1][ni - 2] - num[1][ni]));
			cc = (a*a + b*b - c*c) / (2 * a*b);
			arc = acos(cc) * 180 / 3.1415926;
			if (arc>(double)180||arc<(double)0)
			{
				flag = 1;
			}
		}
		a = sqrt((num[0][ni] - num[0][0])*(num[0][ni] - num[0][0]) + (num[1][ni] - num[1][0])*(num[1][ni] - num[1][0]));
		b = sqrt((num[0][0] - num[0][1])*(num[0][0] - num[0][1]) + (num[1][0] - num[1][1])*(num[1][0] - num[1][1]));
		c = sqrt((num[0][ni] - num[0][1])*(num[0][ni] - num[0][1]) + (num[1][ni] - num[1][1])*(num[1][ni] - num[1][1]));
		cc = (a*a + b*b - c*c) / (2 * a*b);
		arc = acos(cc) * 180 / 3.1415926;
		if (arc>(double)180 || arc<(double)0)
		{
			flag = 1;
		}
		if (flag = 0)
		{
			printf("convexn");
		}
		if (flag = 1)
		{
			printf("concaven");
		}
	}
	return 0;
}

 


更新下AC代码:

思路是判断相邻两条边的斜率,如果第二条边斜率小于第一条边,则为凹。

 

#include
#include
struct xy
{
    int x;
    int y;
};
typedef struct xy xy;
int main()
{
    xy num[10001],d,z;
    int a, b, c, cc, n, ni;
    int flag;
    while (~scanf("%d",&n)&&n!=0)
    {
        flag = 0;
        for (ni = 0; ni < n; ni++)
        {
            scanf("%d%d", &num[ni].x, &num[ni].y);
        }
        num[ni] = num[0];
        num[ni + 1] = num[1];
        for (ni = 0; ni < n; ni++)
        {
            d.x = num[ni + 1].x - num[ni].x;
            d.y = num[ni + 1].y - num[ni].y;
            z.x = num[ni + 2].x - num[ni + 1].x;
            z.y = num[ni + 2].y - num[ni + 1].y;
            if ((d.x*z.y - d.y*z.x) < 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            printf("convexn");
        }
        if (flag == 1)
        {
            printf("concaven");
        }
    }
    return 0;
}

 


原文标题:HDOJ2108:Shape of HDU|落絮飞雁的个人网站
原文链接:https://www.luoxufeiyan.com/2014/12/15/%e3%80%90%e6%9c%aa%e5%ae%8c%e3%80%91hdoj2108%ef%bc%9ashape-of-hdu/
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。