题目描述
二维坐标上有一些点，保证它们的x坐标互不相同，（y坐标可能相同，可能有3点共线），每个点都有一个权值，表示点i指向点，初始时每个点指向它自己，
模拟过程就是执行以下伪代码：
| 1
2 3 4 5 6 7 8 9 10 |
for i=1 to n do b[i]=i
for i=1 to n do { 输出 b[i];
if（b[i]不等于i）L=连接点i，b[i] 的直线； else L=过点i平行于x轴的直线；
对于任意的x，满足点x在直线L下方（且不在直线上），b[x]=i; } |
现在给定正整数 $n$ 以及这 $n$ 个点的坐标，求这个程序的输出结果。
思路
首先我们不可能真的去模拟啊 233
我们观察一下这道题的计算过程，抛开它的表象，寻求其本质。思考，新加入一个点 $j$ 时，上一个点 $i$ 已经和之前的某个点连出一条直线 $L_i$，如何判断这个点是否被包含了？只要和上一个点连出直线 $L_j$，判断它们的斜率大小即可。$j$ 在 $L_i$ 的下方，当且仅当 $k_j<k_i$。显然，对之后的点产生影响的直线 $L$，其斜率是单调递减的。
所以我们可以用一个单调队列维护所有的直线，加入一个新点时，暴力判断这个点将与之前的哪一个点连边。如果找不到这样的点，单独判断伪代码中 L=过点i平行于x轴的直线； 这一情况即可。
代码
#include <bits/stdc++.h>
#define maxn 1001000
int x[maxn],y[maxn],q[maxn],hq,n;
inline bool check(int a,int b,int c){
return 1ll*(y[a]-y[b])*(x[b]-x[c])>=1ll*(y[b]-y[c])*(x[a]-x[b]);
}
int main(){
scanf("%d",&n);
for (register int i=1;i<=n;++i)
scanf("%d%d",x+i,y+i);
for (register int i=1;i<=n;++i){
while(hq>1&&check(i,q[hq],q[hq-1])) hq--;
if (hq==1&&y[i]>=y[q[hq]]) hq=0;
printf("%d\n",hq?q[hq]:i);
q[++hq]=i;
}
}