View Code of Problem 1092

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define PI 3.1415926

const double eps=1e-12;
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))

using namespace std;
const int MAXN = 1010;

struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
        x = _x;
        y = _y;
    }
    Point operator -(const Point &b)const {
        return Point(x - b.x,y - b.y);
    }
//叉积
    double operator ^(const Point &b)const {
        return x*b.y - y*b.x;
    }
//点积
    double operator *(const Point &b)const {
        return x*b.x + y*b.y;
    }
//绕原点旋转角度B（弧度值），后x,y的变化
    void transXY(double B) {
        double tx = x,ty = y;
        x = tx*cos(B) - ty*sin(B);
        y = tx*sin(B) + ty*cos(B);
    }
};
Point L[MAXN];
int Stack[MAXN],top;
int n;
double m;

double dist(Point a,Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int sgn(double x) {
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    return 1;
}
//相对于L[0]的极角排序
bool _cmp(Point p1,Point p2) {
    double tmp = (p1-L[0])^(p2-L[0]);
    if(sgn(tmp) > 0)return true;
    else if(sgn(tmp) == 0 && sgn(dist(p1,L[0]) - dist(p2,L[0])) <= 0)
        return true;
    else return false;
}
void Graham(int n) {
    Point p0;
    int k = 0;
    p0 = L[0];
//找最下边的一个点
    for(int i = 1; i < n; i++) {
        if( (p0.y > L[i].y) || (p0.y == L[i].y && p0.x > L[i].x) ) {
            p0 = L[i];
            k = i;
        }
    }
    swap(L[k],L[0]);
    sort(L+1,L+n,_cmp);
    if(n == 1) {
        top = 1;
        Stack[0] = 0;
        return;
    }
    if(n == 2) {
        top = 2;
        Stack[0] = 0;
        Stack[1] = 1;
        return ;
    }
    Stack[0] = 0;
    Stack[1] = 1;
    top = 2;
    for(int i = 2; i < n; i++) {
        while(top > 1 && sgn((L[Stack[top-1]]-L[Stack[top-2]])^(L[i]-L[Stack[top-2]])) <= 0)
            top--;
        Stack[top++] = i;
    }
}

int main() {
    //freopen("test.in","r",stdin);
    n=0;
    while(~scanf("%lf%lf",&L[n].x,&L[n].y)) {
        n++;
    }
    Graham(n);
    double ans=0;
    int p=0;
    for(int i=0; i<top; i++) {
        int u=Stack[i];
        if(L[u].x==0&&L[u].y==0) {
            p=i;
            break;
        }
    }
    for(int i=p; i<top; i++)
        printf("(%.0f,%.0f)\n",L[Stack[i]].x,L[Stack[i]].y);
    for(int i=0; i<p; i++) {
        printf("(%.0f,%.0f)\n",L[Stack[i]].x,L[Stack[i]].y);
    }
    return 0;
}