HDU6325 Interstellar Travel 凸包+思维

1.题意：有n个点，起点为(0,0)，终点为(xn,0) ，从当前点A到下一个点B的代价为： A.x*B.y - B.x*A.y ，要求找到一条路径，使得走该条路的总花费最小。

2.分析：

（1）一定注意：起点为(0,0), 终点也在x轴上！每个点P ，相当于向量OP。所以代价相当于两个连向原点的向量的叉乘。

（2）从当前点到下一个点，如果为顺时针方向，则叉乘结果为负，如果为逆时针，则为正。所以为了使结果最小，所以尽量使所有点按照顺时针方向排列。

（3）可以大体画一个图：

HDU6325 Interstellar Travel 凸包+思维

我们发现这样叉乘起来的结果正好是一个多边形的面积（负向）！而且为了使结果最小，应该使面积最大，这不就是凸包吗！所以我们需要构建一个上凸包。

（4）注意：题目要求字典序最小，所以：

对于重复点，我们只保存前面的

对于一条线的点，如果当前点编号<前一个点，则删除前一个点。否则加入当前点

一定要开double !! 会爆int。。。

3.代码：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 10;
map<pair<int,int>,int> ID;
struct Point{
   double x,y;
   int id;
   Point(double _x = 0,double _y = 0):x(_x),y(_y) {}
   bool operator<(const Point&another)const{
        if(x==another.x&&y==another.y)return id<another.id;
        if(x==another.x)return y<another.y;
        return x<another.x;
   }
}point[maxn],ch[maxn];
typedef Point Vector;
Vector operator+(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator-(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
double Cross(Vector A,Vector B){
    return A.x*B.y - B.x*A.y;
}
int Andrew(int len){
    int m = 0;
    for(int i = 0;i<len;i++){
        if(m>=1&&point[i].x==ch[m-1].x&&point[i].y==ch[m-1].y)continue;
        while(m>1&&Cross(ch[m-1]-ch[m-2],point[i]-ch[m-2])>=0){
            if(m>1&&Cross(ch[m-1]-ch[m-2],point[i]-ch[m-2])>0)m--;
            else if(m>1&&Cross(ch[m-1]-ch[m-2],point[i]-ch[m-2])==0&&point[i].id<ch[m-1].id)m--;
            else break;
        }
        ch[m++] = point[i];
    }
    return m;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i = 0;i<n;i++){
            scanf("%lf%lf",&point[i].x,&point[i].y);
            point[i].id = i+1;
        }
        sort(point,point+n);
        int ans = Andrew(n);
        for(int i = 0;i<ans;i++){
            if(i!=0)printf(" ");
            printf("%d",ch[i].id);
        }
        printf("\n");
    }
    return 0;
}

HDU6325 Interstellar Travel 凸包+思维

相关推荐