【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;
}
}