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;
}