Scrambled Polygon POJ - 2007 

题意: 从(0,0)开始逆时针输出 凸包

思路 :  极角排序    /     凸包(跑完就是极角序)跑一遍 . 时间复杂度O(nlogn)

极角排序的两种写法
int cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}

bool cmp(point a,point b){
    if(atan2(a.y,a.x)!=atan2(b.y,b.x))
        return atan2(a.y,a.x)<atan2(b.y,b.x);
    else return a.x<b.x;
}

第一种速度慢,但精度高
第二种速度快,但有精度误差
凸包写法

#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=3e5+5;
const int MOD=1e9+7;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int sign(int x){
    return abs(x)<1e-7?0:x<0?-1:1;
}
struct Point{
    int x,y;
    Point(int x=0, int y=0) : x(x), y(y) {}
    Point operator - (const Point &rhs) const{
        return Point(x-rhs.x,y-rhs.y);
    }
    bool operator == (const Point &rhs) const{
        return sign(x-rhs.x)==0&&sign(y-rhs.y)==0;
    }
    bool operator < (const Point &rhs)const{
        if(x==rhs.x)    return y<rhs.y;
        else    return x<rhs.x;
    }
};
typedef Point Vector;
int cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
int n;
typedef vector<Point> Polygon;
Polygon convex_hull(Polygon P){
    sort(P.begin(),P.end());
    P.erase(unique(P.begin(), P.end()), P.end());
    int n=P.size(),k=0;
    Polygon Q(n*2);
    for(int i=0;i<n;++i){  /// 构造下凸包
        while(k>1&&cross(Q[k-2]-Q[k-1],Q[k-2]-P[i])<=0) k--;
            Q[k++]=P[i];
    }
    int t=k;
    for(int i=n-2;i>=0;--i){
        while(k>t && cross(Q[k-2]-Q[k-1],Q[k-2]-P[i])<=0)   k--;
        Q[k++]=P[i];
    }
    Q.resize(k-1);
    return Q;
}

int main(void){
    Polygon t;
    int x,y;
//    int cnt=0;
    while((scanf("%d%d",&x,&y))==2){
        t.push_back({x,y});
//        ++cnt;
//        if(cnt==10) break;
    }
//    cout <<"here" << endl;
    vector<Point> ans=convex_hull(t);
    int pos;
    for(int i=0;i<(int)ans.size();i++){
        if(ans[i]==Point(0,0)){
            pos=i;
            break;
        }
    }
    for(int i=pos;i<(int)ans.size();i++)  printf("(%d,%d)\n",ans[i].x,ans[i].y);
    for(int i=0;i<pos;i++)  printf("(%d,%d)\n",ans[i].x,ans[i].y);
    return 0;
}

极角排序写法
#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=3e5+5;
const int MOD=1e9+7;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int sign(int x){
    return abs(x)<1e-7?0:x<0?-1:1;
}
struct Point{
    int x,y;
    Point(int x=0.0, int y=0.0) : x(x), y(y) {}
    Point operator - (const Point &rhs) const{
        return Point(x-rhs.x,y-rhs.y);
    }
    bool operator == (const Point &rhs) const{
        return sign(x-rhs.x)==0&&sign(y-rhs.y)==0;
    }
    bool operator < (const Point &rhs)const{
        if(x==rhs.x)    return y<rhs.y;
        else    return x<rhs.x;
    }
};
typedef Point Vector;
int cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
int n;
typedef vector<Point> Polygon;
Polygon convex_hull(Polygon P){
    sort(P.begin(),P.end());
    P.erase(unique(P.begin(), P.end()), P.end());
    int n=P.size(),k=0;
    Polygon Q(n*2);
    for(int i=0;i<n;++i){
        while(k>1&&cross(Q[k-2]-Q[k-1],Q[k-2]-P[i])<=0) k--;
            Q[k++]=P[i];
    }
    int t=k;
    for(int i=n-2;i>=0;--i){
        while(k>t && cross(Q[k-2]-Q[k-1],Q[k-2]-P[i])<=0)   k--;
        Q[k++]=P[i];
    }
    Q.resize(k-1);
    return Q;
}
bool cmp(Point a, Point b)  {
    return cross (a, b) > 0;
}
int main(void){
    Polygon t;
    int x,y;
    while((scanf("%d%d",&x,&y))==2){
        t.push_back(Point(x,y));
    }
//    cout <<"here" << endl;
    sort(t.begin()+1,t.end(),cmp);
//    vector<Point> ans=convex_hull(t);
    for(int i=0;i<(int)t.size();++i)   printf("(%d,%d)\n",t[i].x,t[i].y);
    return 0;
}