HDU 6325 Problem G. Interstellar Travel（上凸包）

Description

给出n$n$个二维点的坐标(xi,yi)$(x_i,y_i)$，要求从第一个点出发经过若干点到达最后一个点使得代价最小，从(xi,yi)$(x_i,y_i)$点到(xj,yj)$(x_j,y_j)$需要满足i<j,xi<xj$i<j,x_i<x_j$，代价为xi⋅yj−xj⋅yi$x_i\cdot y_j-x_j\cdot y_i$，要求选择字典序最小的点集使得代价最小

Input

第一行一整数T$T$表示用例组数， 每组用例首先输入一整数n$n$表示点数，之后n$n$行每行输入两个整数xi,yi$x_i,y_i$表示第i$i$个点的横纵坐标

(1≤T≤10,2≤n≤2⋅105,y1=yn=0,x1<x2,...,xn−1<xn)$(1\le T\le 10,2\le n\le 2\cdot {10}^5,y_1=y_n=0,x_1<x_2,...,x_{n-1}<x_n)$

Output

输出所选点集

Sample Input

1
3
0 0
3 0
4 0

Sample Output

1 2 3

Solution

显然分值和为所选点集构成的多边形面积，故选取上凸包上的点即可，由于结果要字典序最小，故要注意点共线的情况和重点的情况，因为此时凸包不是完全凸的，那么重点会影响凸性

Code

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define maxn 200005
struct Point 
{
    int x,y,id;
    Point(){};
    Point(int _x,int _y,int _id)
    {
        x=_x,y=_y,id=_id;
    }
    Point operator-(const Point &b)const
    {
        return Point(x-b.x,y-b.y,0);
    }
    ll operator^(const Point &b)const
    {
        return 1ll*x*b.y-1ll*y*b.x;
    }
    bool operator<(const Point &b)const
    {
        if(x!=b.x)return x<b.x;
        if(y!=b.y)return y<b.y;
        return id<b.id;
    }
}p[maxn],s[maxn];
int T,n;
void convex_hull()
{
    int top=0;
    for(int i=1;i<=n;i++)
    {
        if(i>1&&p[i].x==p[i-1].x&&p[i].y==p[i-1].y)continue;
        while(top>1&&((s[top-1]-s[top-2])^(p[i]-s[top-1]))>0)top--;
        while(top>1&&((s[top-1]-s[top-2])^(p[i]-s[top-1]))==0&&s[top-1].id>p[i].id)top--;
        s[top++]=p[i];
    }
    for(int i=0;i<top;i++)
        printf("%d%c",s[i].id,i==top-1?'\n':' ');
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].id=i;
        }
        sort(p+1,p+n+1);
        convex_hull();
    }
    return 0;
}