首页 > ACM题库 > HDU-杭电 > hdu 2108 Shape of HDU-凸包问题-[解题报告]cpp:showcolumns
2013
12-29

hdu 2108 Shape of HDU-凸包问题-[解题报告]cpp:showcolumns

Shape of HDU

问题描述 :

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

输入:

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

输出:

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

样例输入:

4
0 0 1 0 1 1 0 1
0

样例输出:

convex


海东集团终于顺利成立了!后面的路,他们会顺顺利利吗?
欲知后事如何,且听下回分解――

http://acm.hdu.edu.cn/showproblem.php?pid=2108

#include<iostream>
using namespace std;

typedef struct 
{
    double x;
    double y;
}Point;
Point p[1010];

int main()
{
    int n, i;
    while(cin >> n, n){
        bool flag = true;
        double sum = 0;
        for(i = 0; i < n; i++)
            cin >> p[i].x >> p[i].y;

        p[n].x = p[0].x, p[n].y = p[0].y;
        p[n + 1].y = p[1].x, p[n + 1].y = p[1].y;
        for(i = 0; i < n; i++)
        {
            sum = (p[i + 1].x  - p[i].x) * (p[i + 2].y - p[i].y) - ( p[i + 1].y - p[i].y) * (p[i + 2].x - p[i].x);
            if(sum < 0)
            {
                flag = false;
                break;
            }
        }
        if(flag)
            puts("convex");
        else
            puts("concave");
    }
    return 0;
}

解题转自:http://blog.csdn.net/welon123/article/details/6025542


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。