[UVA] 681 - Convex Hull Finding
Convex Hull Finding
| 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 512
512, 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;
}