【JZOJ 5950】虐暴全场 / 题解

题目描述

二维坐标上有一些点,保证它们的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;
    }
}
Show Comments