hdu6325 /// 上凸包

题目大意：

给定n 为n个点

给定n个点的坐标

两个点(xi,yi) (xj,yj)之间的花费是 xi*yj-yi*xj （可能为负数）

要求从点1经过若干个点到点n最小花费的路径且路径要按x轴方向（即x递增）

输出路径顺序经过的点的编号

使花费最小而花费又可能为负数那么就尽量使得花费为负数

所以点的方向一直为顺时针的话就能使得花费最小也就是一个上凸包

题解：https://www.cnblogs.com/mountaink/p/9591414.html

BTW 这题似乎没有考虑精度误差加上精度误差的判断反而会WA

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define LL long long

#define mem(i,j) memset(i,j,sizeof(i))

using namespace std;

const int N=2e5+;

const int MOD=1e9+;

const double EPS=1e-;

struct P {

    double x,y; int id=;

    P(){} P(double x,double y):x(x),y(y){}

    P operator -(P p) { return P(x-p.x,y-p.y); }

    P operator +(P p) { return P(x+p.x,y+p.y); }

    double dot(P p) { return x*p.x+y*p.y; }

    double det(P p) { return x*p.y-y*p.x; }

    bool operator <(const P& p)const {

        if(x!=p.x) return x<p.x;

        if(y!=p.y) return y<p.y;

        return id<p.id;

    }

    bool operator ==(const P& p)const {

        return x==p.x && y==p.y;

    }

    void scf() { scanf("%lf%lf",&x,&y); }

}p[N], ans[N];

int n;

int andrew() {

    sort(p+,p++n);

    int c=;

    for(int i=;i<=n;i++) {

        if(i> && p[i]==ans[c-]) continue;

        while(c> && (p[i]-ans[c-]).det(ans[c-]-ans[c-])>=) {

            if((p[i]-ans[c-]).det(ans[c-]-ans[c-])>) c--;

            else if(ans[c-].id>p[i].id) c--;

            else break;

        }

        ans[c++]=p[i];

    }

    return c;

}

int main()

{

    int t; scanf("%d",&t);

    while(t--) {

        scanf("%d",&n);

        for(int i=;i<=n;i++) p[i].scf(), p[i].id=i;

        int c=andrew();

        for(int i=;i<c-;i++)

            printf("%d ",ans[i].id);

        printf("%d\n",ans[c-].id);

    }

    return ;

}

巴特西

hdu6325 /// 上凸包

最新文章

热门文章