1012 寻找凸包

Dear 丶 2022-09-11 15:21 228阅读 0赞

**Description**

给定平面上N个点, 请找出这N个点的凸包.

**Input**

第一行输入M表示包含M组测试数据，每组先输入N (N<=100), 接着输入N个坐标(x,y), x和y均为int型整数.

**Output**

以最下最左点开始逆时针输出凸包, 若有多个点在同一坐标,只输出一个,若凸包上有多个点在同一线上,只输出两端点.

**Sample Input**

2
    7 1 1 4 1 4 4 4 4 1 4 2 2 5 5
    8 5 6 8 3 1 8 5 7 3 5 3 5 1 8 2 11

**Sample Output**

case 1:
    1 1
    4 1
    5 5
    1 4
    case 2:
    8 3
    2 11
    1 8
    3 5
    
    示例代码:
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    struct position_t {
        int x;
        int y;
        double angle;
        double len;
    } pos[2001], stack[2001];
    int n;
    int top;
    
    
    int cmp_yx (const void * a, const void * b) {
        position_t *p1 = (position_t *)a;
        position_t *p2 = (position_t *)b;
        if(p1->y != p2->y) {
            return p1->y - p2->y;
        }
        else {
            return p1->x - p2->x;
        }
    }
    
    int cmp_angle (const void * a, const void * b) {
        position_t *p1 = (position_t *)a;
        position_t *p2 = (position_t *)b;
        if(p1->angle - p2->angle > 0) {
            return 1;
        }
        else if(p1->angle - p2->angle < 0) {
            return -1;
        }
        else {
            if(p1->len - p2->len > 0) {
                return 1;
            }
            else if(p1->len - p2->len < 0) {
                return -1;
            }
            else {
                return 0;
            }
        }
    }
    
    int push(int i) {
        stack[top].x = pos[i].x;
        stack[top].y = pos[i].y;
        stack[top].angle = pos[i].angle;
        top++;
        return top;
    }
    
    int initstack() {
        top = 0;
    }
    
    int pop() {
        top--;
        return top;
    }
    
    int isright(int a, int b, int x, int y) {
        if(a*y-b*x > 0) {
            return 0;
        }
        return 1;
    }
    int canpop(int i) {
        if(top<=2) {
            return 0;
        }
        if(isright(stack[top-1].x-stack[top-2].x, stack[top-1].y-stack[top-2].y, pos[i].x-stack[top-2].x, pos[i].y-stack[top-2].y)) {
            return 1;
        }
        return 0;
    }
    int isonline(int a, int b, int x, int y) {
        if(a*y-b*x ==0) {
            return 1;
        }
        return 0;
    }
    
    int findp0() {
        int minx = 2147483647;
        int miny = 2147483647;
        int idx = 0;
        for(int i=0; i<n; i++) {
            if(pos[i].y < miny) {
                miny = pos[i].y;
                idx = i;
            }
        }
        for(int i=0; i<n; i++) {
            if(pos[i].y==miny && pos[i].x<minx) {
                minx = pos[i].x;
                idx = i;
            }
        }
        return idx;
    }
    
    void sortangle() {
        for(int i=1; i<n; i++) {
            pos[i].len = sqrt((pos[i].y-pos[0].y)*(pos[i].y-pos[0].y)+(pos[i].x-pos[0].x)*(pos[i].x-pos[0].x));
            pos[i].angle = acos((pos[i].x-pos[0].x)/pos[i].len);
            
        }
        qsort(&pos[1], n-1, sizeof(position_t), cmp_angle);
    }
    
    void removesame() {
        qsort(pos, n, sizeof(position_t), cmp_yx);
        int k=0;
        for(int i=1; i<n; i++) {
            if(pos[i].x==pos[k].x && pos[i].y==pos[k].y) {
            }
            else {
                k++;
                pos[k].x = pos[i].x;
                pos[k].y = pos[i].y;
            }
        }
        n = k+1;
    }
    
    int solve() {
        scanf("%d", &n);
        for(int i=0; i<n; i++) {
            scanf("%d%d", &pos[i].x, &pos[i].y);
        }
        
        removesame();
        
        int idx = findp0();
        
        position_t temppos = pos[idx];
        for(int i=idx; i>0; i--) {
            pos[i] = pos[i-1];
        }
        pos[0] = temppos;
        
        sortangle();
        
        initstack();
        push(0);
        int k = 2;
        for(; k<n; k++) {
            if(!isonline(pos[k].x-pos[0].x, pos[k].y-pos[0].y, pos[1].x-pos[0].x, pos[1].y-pos[0].y)) {
                break;
            }
        }
        push(k-1);
        push(k);
        for(int i=k+1; i<n; i++) {
            while(canpop(i)) {
                pop();
            }
            push(i);
        }
        
        for(int i=0; i<top; i++) {
            printf("%d %d\n", stack[i].x, stack[i].y);
        }
        
        return 0;
    }
    
    int main() {
        int m;
        scanf("%d", &m);
        for(int i=0; i<m; i++) {
            printf("case %d:\n", i+1);
            solve();
        }
        return 0;
    }