题目描述

二维坐标上有一些点,保证它们的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轴的直线; 这一情况即可。

代码