Convex Hull Finding

Given a single connected contour, which is either convex or non-convex (concave), use any algorithm to find its Convex Hull, i.e., the smallest convex contour enclosing the given shape. If the given contour is convex, then its convex hull is the original contour itself. The maximal size of the shape is 512512, and the maximal number of the vertices of the shape is 512. Write a program to read the input data (the given shapes) from a disk file, implement your convex hull finding algorithm, and then output the shape data of the results to the standard output.

Input 

The order of the vertices is counterclockwise in X-Y Cartesian Plane (if you consider the origin of the display window is on the upper-left corner, then the orientation of the vertices is clockwise), and none of the neighboring vertices are co-linear. Since all the shapes are closed contours, therefore, the last vertex should be identical to the first vertex. There are several sets of data within a given data file. The negative number -1 is used to separate the data set.

Line	Data in
Number	the File	Explanation
1	K	a positive integer showing how many sets of data in this file
2	N	a positive integer showing the number of vertices for the shape
3		two positive integers for the first vertex (X1, Y1)
4		two positive integers for the next neighboring vertex (X2, Y2)
...
N+2		two positive integers for the last vertex (XN, YN)
N+3	-1	Delimiter
N+4	M	a positive integer showing the number of vertices for the next shape
N+5		two positive integers for the first vertex
...

Note: Please note that the Line Number, Data in the File and Explanation are not given in the file. They are shown here only to assist you in reading the data.

Output 

Output the convex hull of all K input shapes to the standard output. The data format should be the same as the input file. In addition, the vertex with the smallest Y value should be the first point and if there are points with the same Y value, then the smallest X value within those points should be the first point.

Sample Input 

3
15
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35
30 30
-1
12
50 60
60 20
70 45
100 70
125 90
200 113
250 140
180 170
105 140
79 140
60 85
50 60
-1
6
60 20
250 140
180 170
79 140
50 60
60 20

Sample Output 

3
8
60 20
250 50
300 200
130 240
76 150
47 76
30 30
60 20
-1
6
60 20
250 140
180 170
79 140
50 60
60 20
-1
6
60 20
250 140
180 170
79 140
50 60
60 20

---

作法 : 單調鍊

凸包複習 !

#include<stdio.h>
#include<stdlib.h>
#define maxP 300000
typedef struct {
    int x, y;
}Point;
Point P[maxP], CH[maxP<<1];
int cmp(const void *i, const void *j) {
    Point *a, *b;
    a = (Point *)i, b = (Point *) j;
    if(a->y != b->y)
        return a->y - b->y;
    return a->x - b->x;
}
int Cross(Point *o, Point *a, Point *b) {
    return (a->x - o->x)*(b->y - o->y) - (a->y - o->y)*(b->x - o->x);
}
void Print(int N, Point CH[]) {
    int i;
    for(i = 0; i < N; i++)
        printf("%d %d\n", CH[i].x, CH[i].y);
}
void ConvexHull(int N, Point P[]) {
    qsort(P, N, sizeof(Point), cmp);
    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];
    }
    printf("%d\n", m);
    Print(m, CH);
}
int main() {
    int K, N, i;
    scanf("%d", &K);
    printf("%d\n", K);
    while(K--) {
        scanf("%d", &N);
        for(i = 0; i < N; i++)
            scanf("%d %d", &P[i].x, &P[i].y);
        if(K)    scanf("%d", &i);
        ConvexHull(N, P);
        if(K)    puts("-1");
    }
    return 0;
}