2014-05-31

UVa 675 - Convex Hull of the Polygon

1. Problem
2. Input file
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

Suppose that a polygon is represented by a set of integer coordinates, {(x0, y0), (x1, y1), (x2, y2), …, (xn, yn), (x0, y0)}. Please find the convex hull of the polygon, where a convex hull is the minimum bounding convex polygon and “convex” means the angle between two consecutive edges is less than 180o.

Input file

Input consists of several datasets separated by a blank line. Each dataset contains a sequence of integer coordinates xi, yi, one in each line. All input sequence will contain at least 3 different points.

Output

The output for each dataset should contain a sequence of integer coordinates xi, yi specifying the convex hull, each in a line. The first coordinate of the output sequence must be the first coordinate in the input sequence that belongs to the convex hull. The output sequence must be in counter-cockwise order. Print a blank line between datasets.

Sample Input

0, 0
2, 0
1, 1
2, 2
0, 2
0, 0

Sample Output

0, 0
2, 0
2, 2
0, 2
0, 0

Solution

題目相當單純要輸出凸包的結果，但是最痛恨的是輸出格式，要求從輸入順序中最小的開始打印。

莫名其妙地弄了很多 WA 出來，也許輸入有重複點的關係，所以把點附加輸入編號可能會有所錯誤，總是暴力查找一個哪個點是要開始打印的即可。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
        x(a), y(b) {}
    bool operator <(const Pt &a) const {
        if(x != a.x)       
            return x < a.x;
        return y < a.y;
    }   
    bool operator ==(const Pt &a) const {
        return x == a.x && y == a.y;
    }
};
int cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
    sort(p, p+n);
    int i, m = 0, t;
    for(i = 0; i < n; i++) {
        while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    for(i = n-1, t = m+1; i >= 0; i--) {
        while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
            m--;
        ch[m++] = p[i];
    }
    return m - 1;
}
Pt D[100005], C[100005<<1], p;
Pt I[100005];
int main() {
    int cases = 0;
    char s[1024];
    while(gets(s)) {
        if(cases++ > 0)
            puts("");
        int n = 0, m, x, y;
        sscanf(s, "%d, %d", &x, &y);
        I[n] = D[n] = Pt(x, y);
        n++;
        while(gets(s) && s[0] != '\0') {
            sscanf(s, "%d, %d", &x, &y);
            I[n] = D[n] = Pt(x, y);
            n++;
        }
        m = monotone(n, D, C);
        int mark = -1;
        for(int i = 0; i < n && mark == -1; i++) {
            for(int j = 0; j < m; j++)
                if(C[j] == I[i]) {
                    mark = j;
                    break;
                }
        }
        for(int i = mark; i < m; i++)
            printf("%d, %d\n", C[i].x, C[i].y);	
        for(int i = 0; i <= mark; i++)
            printf("%d, %d\n", C[i].x, C[i].y);	
    }
    
    return 0;
}

Morris' Blog