POJ - 1696 Space Ant

传送门：Space Ant

题意

给出n个点，有一个小人，他每次只能往左边拐，并且不能走以前走过的路，走的路线也不能相交，问他怎么走可以走的路程最大。

题解

可以想到肯定是所有的点都走到路径会最大，然后就很容易想到这不就可以一直凸包了吗！！每次形成凸包的点删掉再继续凸包，然后每次把点的编号加入队列中，直到没有点没被走过。我用的是graham算法的凸包，先找到纵坐标最小的点，第一次按照极角排序是判断和该点连线的极角，后边都是和前一次凸包里的最后一个点的连线形成的极角判断。（想法很简单，实现好麻烦....）

代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<math.h>
#include<iostream>
#define ll long long
using namespace std;

const ll maxn=1e3+10;

struct node
{
    ll x,y;
    ll id;
}p[maxn],s[maxn],q[maxn];

ll xx,yy;

ll cross(node a,node b,node c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

ll cmp1(node a,node b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}

ll cmp2(node a,node b)
{
    if(atan2(a.y-yy,a.x-xx)-atan2(b.y-yy,b.x-xx)==0) return a.x<b.x;
    else return atan2(a.y-yy,a.x-xx)<atan2(b.y-yy,b.x-xx);
}

queue<ll>qq;
bool vis[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        memset(vis,0,sizeof(vis));
        while(!qq.empty()) qq.pop();
        ll n;
        cin>>n;
        for(ll i=0;i<n;i++){
            cin>>q[i].id>>q[i].x>>q[i].y;
            p[i]=q[i];
        }
        sort(q,q+n,cmp1);
        ll id;
        xx=q[0].x,yy=q[0].y,id=q[0].id;
        qq.push(q[0].id);
        vis[q[0].id]=1;
        while(1){
            ll l=0;
            for(ll i=0;i<n;i++) if(!vis[q[i].id]) p[l++]=q[i];
//            cout<<l<<endl;
            if(!l) break;
            sort(p,p+l,cmp2);
            if(l==1) {qq.push(p[0].id);break;}
            else if(l==2) {qq.push(p[0].id),qq.push(p[1].id);break;}
            else{
                s[0].x=xx,s[0].y=yy,s[0].id=id;s[1]=p[0];
                ll top=1;
                for(ll i=1;i<l;i++){
                    while(top&&cross(s[top-1],s[top],p[i])<=0) top--;    //<=可以去掉重边
                    //如果是向右转，这个中间点就不是我们要找的点
                    s[++top]=p[i];//如果是向左转，就加进来
                }
                for(ll i=0;i<=top;i++){
                    if(!vis[s[i].id]) qq.push(s[i].id);
                    vis[s[i].id]=1;
                }
                xx=s[top].x,yy=s[top].y,id=s[top].id;
            }
        }
        cout<<qq.size();
        while(!qq.empty()) {
            cout<<' '<<qq.front();
            qq.pop();
        }
        cout<<endl;
    }
    return 0;
}