hdu6325 Problem G. Interstellar Travel

题意：定义一个平面 很多点 两点之间的权值为原点为起点的向量做叉积的值 可以为负 求权值最小的从起点到终点的路线

 

看到题目就日了狗了 这题明显能做的 但是训练的时候看到没什么人做 最后也只有87个人过所以之后也没补。。

 

Andrew扫个上凸包 注意一下判重的细节即可

（数组开小了g++返回tle找了1个小时又是另外一个日了狗的故事了）

#include <algorithm>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
const int N=1e6+100;
struct Point{
    int id;
    ll x,y;
    Point(ll _x,ll _y){x=_x;y=_y;}
    Point(){}
    Point operator-(const Point&b)const
    {
        return Point(x-b.x,y-b.y);
    }
    Point operator+(const Point&b)const
    {
        return Point(x+b.x,y+b.y);
    }
    ll operator^(const Point&b)const
    {
        return x*b.y-y*b.x;
    }
    ll operator*(const Point&b)const
    {
        return x*b.x+y*b.y;
    }
    bool operator<(const Point&b)
    {
        if(x==b.x)
        {
            if(y==b.y)
                return id<b.id;
            return y<b.y;
        }
        return x<b.x;
    }
    bool operator==(const Point&b)
    {
        return x==b.x&&y==b.y;
    }
}p[N];
Point ch[N];
bool Che(Point a,Point b,Point c)
{
    if(((c-a)^(b-a))<0)return 1;
    if(((c-a)^(b-a))==0)return c.id<b.id;
    return 0;
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lld%lld",&p[i].x,&p[i].y);
            p[i].id=i+1;
        }
        sort(p,p+n);
        int m=0;
        for(int i=0;i<n;i++)
        {
            if(i&&p[i]==p[i-1])continue;
            while(m>1&&Che(ch[m-2],ch[m-1],p[i]))
                m--;
            ch[m++]=p[i];
        }
        for(int i=0;i<m-1;i++)
            printf("%d ",ch[i].id);
        printf("%d\n",ch[m-1].id);
    }
    return 0;
}