落絮飞雁的个人网站

顺流而下,把梦做完

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:

 


更新下AC代码:

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

 

 


原始链接:HDOJ2108:Shape of HDU|落絮飞雁的个人网站
授权协议:创作共用 署名-非商业性使用 2.5 中国大陆
除注明外,本站文章均为原创;转载时请保留上述链接。