HDU 6325 Interstellar Travel [돌출]

제목 링크
Problem Description
After trying hard for many years, Little Q has finally received an astronaut license. To celebrate the fact, he intends to buy himself a spaceship and make an interstellar travel. Little Q knows the position of n planets in space, labeled by 1 to n. To his surprise, these planets are all coplanar. So to simplify, Little Q put these n planets on a plane coordinate system, and calculated the coordinate of each planet (xi,yi). Little Q plans to start his journey at the 1-th planet, and end at the n-th planet. When he is at the i-th planet, he can next fly to the j-th planet only if xi < xj, which will cost his spaceship xi×yj−xj×yi units of energy. Note that this cost can be negative, it means the flight will supply his spaceship. Please write a program to help Little Q find the best route with minimum total cost.
Input
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases. In each test case, there is an integer n(2≤n≤200000) in the first line, denoting the number of planets. For the next n lines, each line contains 2 integers xi,yi(0≤xi,yi≤109), denoting the coordinate of the i-th planet. Note that different planets may have the same coordinate because they are too close to each other. It is guaranteed that y1=yn=0,0=x1 < x2,x3,…,xn−1 < xn.
Output
For each test case, print a single line containing several distinct integers p1,p2,…,pm(1≤pi≤n), denoting the route you chosen is p1→p2→…→pm−1→pm. Obviously p1 should be 1 and pm should be n. You should choose the route with minimum total cost. If there are multiple best routes, please choose the one with the smallest lexicographically. A sequence of integers a is lexicographically smaller than a sequence of b if there exists such index j that ai=bi for all i < j, but aj < bj.
Sample Input
1 3 0 0 3 0 4 0
Sample Output
1 2 3
제목
평면 에는 n 개의 점 이 있 는데 1 부터 n 까지 번호 가 있 습 니 다. 지금 은 우주선 을 한 점 에서 다음 점 까지 운항 합 니 다.당신 의 모든 좌 표를 보 여 주 려 면 i 점 에서 j 점 까지 xi < xj 를 요구 해 야 합 니 다.우주선 이 소모 하 는 에 너 지 는 바로 xi * yj - xj * yi 로 소모 치 는 마이너스 가 될 수 있다.지금 은 첫 번 째 점 에서 n 번 째 점 까지 의 최소 소모 상황 에서 우주선 이 지나 간 점 의 번 호 를 출력 하고 사전 순서에 따라 배열 하 라 고 물 었 다.
문제 풀이 의 사고 방향.
문 제 를 보면 두 점 사이 의 차 승 을 구 할 수 있 고 소모 치 는 마이너스 일 수 있 기 때문에 우 리 는 돌출 가방 을 생각 하고 역 돌출 가방 을 만 들 수 있다. 그러면 돌출 가방 옆 에 있 는 점 은 차 승 과 작은 것 에 따라 사전 순서에 따라 출력 하면 된다.
코드 부분

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int qu[maxn],mn[maxn];///qu          
struct node
{
    int x,y,id;
    bool operatorconst node &p)const///  
    {
        if(x!=p.x) return xif(y!=p.y) return y>p.y;
        return idint x,int y,int z)///  xi*yj-xj*yi
{
    int ax=pt[y].x-pt[x].x;
    int ay=pt[y].y-pt[x].y;
    int bx=pt[z].x-pt[y].x;
    int by=pt[z].y-pt[y].y;
    return 1LL*ax*by-1LL*ay*bx;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&pt[i].x,&pt[i].y);
        }
        for(int i=1; i<=n; i++)
        {
            pt[i].id=i;///  
        }
        sort(pt+1,pt+n+1);
        int now=0;///           
        qu[0]=1;///     
        for(int i=2; i<=n; i++)///     
        {
            if(pt[i].x==pt[i-1].x)
                continue;
            while(now&&get(qu[now-1],qu[now],i)>0)
                now--;
            qu[++now]=i;
        }
        int l=0,r;
        printf("1");
        while(lfor(r=l+1; r<=now; r++)
            {
                if(get(qu[l],qu[l+1],qu[r])!=0)///        
                    break;
            }
            mn[r]=1e9;
            for(int i=r-1; i>=l; i--)
            {
                mn[i]=min(pt[qu[i]].id,mn[i+1]);
            }
            for(int i=l+1; i<=r-1; i++)
            {
                if(mn[i]==pt[qu[i]].id)
                    printf(" %d",pt[qu[i]].id);
            }
            l=r-1;
        }
        cout<return 0;
}