Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A simple polygon is a polygon that contains no self-intersecting lines. A convex polygon is a simple polygon with all internal angles less than 180 degrees. For a set of two-dimensional objects, their convex hull is the convex polygon of least area that completely encloses all of the objects. In the figure below, the three solid-lined objects on the left are enclosed in a dotted-line convex polygon, but that polygon is not their convex hull; on the right the same three objects are enclosed by their convex hull.

Determining the convex hull of a set of objects is a fundamental problem in both computer graphics and computational geometry. The object of this problem is to write a program that will report the convex hull of a set of simple polygons. An input file will define several such sets of polygons for which convex hulls should be reported in the output file.

Input 

Each line of the input file will begin with either the letter `S', the letter `P', or the word `END'. Lines starting with `S' begin a new set of polygons. Lines starting with `P' define a polygon in the current set. The word `END' will appear only as the last line of the input file.

Each `S' starting a line will be followed by a single space and then a character string which identifies the set of polygons. Each `P' starting a line will be followed by a single space and then a list of integers delimited by single spaces. The first integer specifies the number of vertices in the polygon, and the remaining integers specify, in counterclockwise order, the (x,y) coordinates of each polygon vertex.

Each set of polygons will contain from 1 to 20 simple polygons. Each polygon will contain from 3 to 20 distinct vertices. Each vertex will be an integer coordinate in the range (-1000,-1000) to (1000,1000). No input polygon will have more than two adjacent collinear points, that is a point will not occur on an edge between two other points.

It may be assumed that all input will be syntactically correct.

Output 

Two lines should be output for each set of polygons. The first line should start with the character string from the input file which identifies the polygon set, followed by the characters `` convex hull:". The second line should list the coordinates of the vertices in the convex hull, each vertex being preceded by a single space and in the format ``(x,y)", where x and y are the integer coordinates of the vertex. The output of the convex hull vertices should begin with the vertex with the largest x-coordinate, ties being resolved by the selecting the smaller y-coordinate. The vertices of the convex hull should be output in counterclockwise order.

Any vertex that is part of an input polygon that is also part of the convex hull should appear in the output. That is to say points should not be eliminated from the convex hull to prevent more than two adjacent points on the hull from being collinear. For example, supposing that (10,1), (10,7) and (10,12) are consecutive points on the convex hull, the point (10,7) should not be removed but rather reported as part of the convex hull.

Sample Input 

S Sample 1
P 5 8 0 8 8 0 8 5 6 2 3
P 3 6 13 2 18 2 13
P 4 15 6 15 14 10 14 10 6
S Sample 2
P 8 1 2 -3 5 1 8 -3 12 -7 8 -3 5 -7 2 -3 -2
S Sample 3
P 4 150 100 150 150 100 150 100 100
P 4 180 130 180 180 130 180 130 130
S Sample 4
P 4 20 5 10 10 0 5 10 0
P 4 20 20 10 25 0 20 10 15
P 4 20 35 10 40 0 35 10 30
END

Sample Output 

Sample 1 convex hull:
 (15,6) (15,14) (2,18) (0,8) (2,3) (8,0)
Sample 2 convex hull:
 (1,2) (1,8) (-3,12) (-7,8) (-7,2) (-3,-2)
Sample 3 convex hull:
 (180,130) (180,180) (130,180) (100,150) (100,100) (150,100)
Sample 4 convex hull:
 (20,5) (20,20) (20,35) (10,40) (0,35) (0,20) (0,5) (10,0)

---

Miguel A. Revilla
1999-01-11

把所有點做一次凸包即可，用 monotone chain 時，要保留共線的點。


#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Pt {
    long long x, y;
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
long long 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-2, 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;
}
int main() {
    while(getchar() != ' ');
    char cases[105];
    Pt p[10005], ch[10005];
    int i, j, k;
    while(gets(cases)) {
        printf("%s convex hull:\n", cases);
        int n = 0, m;
        while(scanf("%s", cases) == 1) {
            if(cases[0] != 'P')
                break;
            scanf("%d", &m);
            for(i = 0; i < m; i++, n++)
                scanf("%lld %lld", &p[n].x, &p[n].y);
        }
        sort(p, p+n);
        for(i = 1, j = 0; i < n; i++)
            if(p[j].x != p[i].x || p[j].y != p[i].y)
                p[++j] = p[i];
        n = j+1;
        m = monotone(n, p, ch);
        int pos = 0;
        for(i = 0; i < m; i++) {
            if(ch[i].x > ch[pos].x || (ch[i].x == ch[pos].x && ch[i].y < ch[pos].y))
                pos = i;
        }
        for(i = pos; i < m; i++)
            printf(" (%lld,%lld)", ch[i].x, ch[i].y);
        for(i = 0; i < pos; i++)
            printf(" (%lld,%lld)", ch[i].x, ch[i].y);
        puts("");
        if(cases[0] == 'E') break;
        while(getchar() != ' ');
    }
    return 0;
}