输入：
13;-3,-3;1,3;2,-4;6,1;-2,-2;4,5;1,-2;1,4;-2,3;-4,1;-1,1;2,2;1,-1
输出：
-4, 1
-2, 3
4, 5
6, 1
2, -4
-3, -3
#include<iostream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int x[maxn];
int y[maxn];
bool equal(double d1, double d2){
d1 -= d2;
return d1 >= -0.00001 && d1 <= 0.00001;
}
int main(){
//freopen("test.txt", "r", stdin);
int n, i;
int x1 = INT_MAX;// 横坐标最小值
int y1;// 左上角的纵坐标
int x2 = INT_MIN;// 横坐标最大值
int y2;// 右上角的纵坐标
scanf("%d", &n);
for(i = 0; i < n; ++i){
scanf(";%d,%d", x + i, y + i);
if(x[i] < x1){
x1 = x[i];
y1 = y[i];
}else if(x1 == x[i] && y1 < y[i]){
y1 = y[i];
}
if(x[i] > x2){
x2 = x[i];
y2 = y[i];
}else if(x2 == x[i] && y2 < y[i]){
y2 = y[i];
}
}
printf("%d, %d\n", x1, y2);
// 输出上半圈
int cx, cy, lx = x1, ly = y1;
double max_k, k;
while(lx != x2){
max_k = -INT_MIN;
for(i = 0; i < n; ++i){
if(x[i] <= lx){
continue;
}
k = (double)(y[i] - ly) / (x[i] - lx);
if(equal(k, max_k)){// 斜率相同时，取距离远的
if(x[i] > cx){
cx = x[i];
cy = y[i];
}
}else if(max_k < k){
max_k = k;
cx = x[i];
cy = y[i];
}
}
printf("%d, %d\n", cx, cy);
lx = cx;
ly = cy;
}
// 输出与(x2, y2)横坐标相同，纵坐标最小的点（如果有的话）
cy = y2;
for(i = 0; i < n; ++i){
if(x[i] == x2 && cy < y[i]){
cy = y[i];
}
}
if(cy != y2){
printf("%d, %d\n", x2, cy);
}
// 输出下半圈
lx = x2, ly = cy;
while(lx != x1){
max_k = INT_MIN;
for(i = 0; i < n; ++i){
if(x[i] >= lx){
continue;
}
k = (double)(y[i] - ly) / (x[i] - lx);
if(equal(k, max_k)){// 斜率相同时，选择距离远的
if(x[i] < cx){
cx = x[i];
cy = y[i];
}
}else if(max_k < k){
max_k = k;
cx = x[i];
cy = y[i];
}
}
if(cx != x1){
printf("%d, %d\n", cx, cy);
}
lx = cx;
ly = cy;
}
// 输出与(x1, y1)横坐标相同，纵坐标最小的点（如果有的话）
cy = y1;
for(i = 0; i < n; ++i){
if(x[i] == x1 && cy < y[i]){
cy = y[i];
}
}
if(cy != y1){
printf("%d, %d\n", x1, cy);
}
}