gym 101164 H.Pub crawl 凸包

题目链接：http://codeforces.com/gym/101164/attachments

题意：对于已知的 n 个二维坐标点，要求按照某种特定的连线方式将尽可能多的点连接（任意相邻的 3 个点 a , b , c ，点 c 必须在有向线段 ab 的左侧。问最多可以连多少点，并给出连线顺序。

思路：因为连接最多的点，尽量让形成一个凸包将点包起来，形成螺旋式的连接所有的点，凸包模板；

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<stdlib.h>
#include<time.h>
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e5+10,M=1e6+10,inf=2147483647;
const LL INF=1e18+10,mod=2147493647;
const double eps = 1e-8;
const double PI = acos(-1.0);
int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}
struct Point
{
    double x,y;
    int pos;
    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;
    }

}a[N];
double dist(Point a,Point b)
{
    return sqrt((a-b)*(a-b));
}
int n;
const int MAXN = 5010;
Point listt[MAXN];
int Stack[MAXN],top,vis[N]; //相对于listt[0]的极角排序
vector<int>ans;
bool _cmp(Point p1,Point p2)
{
    double tmp = (p1-listt[0])^(p2-listt[0]);
    if(sgn(tmp) > 0)return true;
    else if(sgn(tmp) == 0 && sgn(dist(p1,listt[0]) - dist(p2,listt[0])) <= 0) return true;
    else return false;
}
void Graham()
{
    Point p0;
    int k = 0;
    p0 = listt[0]; //找最下边的一个点
    for(int i = 1; i < n; i++)
    {
        if( (p0.y > listt[i].y) || (p0.y == listt[i].y && p0.x > listt[i].x) )
        {
            p0 = listt[i];
            k = i;
        }
    }
    swap(listt[k],listt[0]);
    sort(listt+1,listt+n,_cmp);
    int m=1;
    Stack[0] = 0;
    Stack[1] = 1;
    vis[0]=1;
    vis[1]=1;
    top = 2;
    while(top<n)
    {
        for(int i = 2; i < n; i++)
        {
            if(vis[i])continue;
            while(top > 1 && sgn((listt[Stack[top-1]]-listt[Stack[top-2]])^(listt[i]-listt[Stack[top-2]])) <= 0)
            top--,vis[Stack[top]]=0;
            Stack[top++] = i;
            vis[i]=1;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lf%lf",&listt[i].x,&listt[i].y),listt[i].pos=i+1;
    Graham();
    printf("%d
",n);
    for(int i=0;i<n;i++)
        printf("%d ",listt[Stack[i]].pos);
    return 0;
}
/*
5
0 4
3 0
7 11
9 1
13 8
*/