深圳网站设计师培训学校,网站建设意识形态,建站平台塔山双喜,社区电商app定制开发多少钱正题
题目链接:https://www.ybtoj.com.cn/contest/116/problem/2 题目大意 nnn个点#xff0c;xxx坐标递增#xff0c;第iii个点向第jjj个点连边。
开始一个人在点sss#xff0c;他会向他看到过的yyy坐标最大的点的方向走#xff08;两个点之间能够看到当且仅当它们之间没…正题
题目链接:https://www.ybtoj.com.cn/contest/116/problem/2 题目大意
nnn个点xxx坐标递增第iii个点向第jjj个点连边。
开始一个人在点sss他会向他看到过的yyy坐标最大的点的方向走两个点之间能够看到当且仅当它们之间没有边或者点。
求对于每个sss走到yyy坐标最大的点的经过点数。
yyy值同样的以编号大的算大
1≤n≤5×105,1≤xi,yi≤1061\leq n\leq 5\times 10^5,1\leq x_i,y_i\leq 10^61≤n≤5×105,1≤xi,yi≤106 解题思路
先考虑每个点能看到的最高的点。
维护一个前缀的上凸壳然后每次把该点连接的那个点就是这个点在凸壳方向能看到的最高的点。
左右各做一次就好了。
然后考虑怎么处理答案先把所有点按照目标点的高度排序然后每个点找到它的方向上在它前面的第一个点作为它的真正目标点。然后倒序转移就好了。
找真正目标点的过程可以反过来然后用链表实现
时间复杂度O(nlogn)O(n\log n)O(nlogn)写基排就O(n)O(n)O(n)了 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e510;
ll n,x[N],y[N],pos[N],s[N],l[N],r[N],p[N],f[N];
ll xj(ll a,ll b,ll c){ll x1x[b]-x[a],y1y[b]-y[a];ll x2x[c]-x[a],y2y[c]-y[a];return x1*y2-x2*y1;
}
bool cmp(ll a,ll b){return y[p[a]]*np[a]y[p[b]]*np[b];
}
signed main()
{
// freopen(mountain.in,r,stdin);
// freopen(mountain.out,w,stdout);scanf(%lld,n);for(ll i1;in;i)scanf(%lld%lld,x[i],y[i]),pos[i]i;ll top0;s[top]1;for(ll i2;in;i){while(top1xj(s[top-1],s[top],i)0)top--;p[i]s[top];s[top]i;}top1;s[top]n;for(ll in-1;i1;i--){while(top1xj(s[top-1],s[top],i)0)top--;if(y[s[top]]y[p[i]])p[i]s[top];s[top]i;}for(ll i1;in;i)if(y[p[i]]*np[i]y[i]*ni)p[i]0;y[0]1e9;sort(pos1,pos1n,cmp);for(ll i1;in;i)l[i]i-1,r[i]i1;for(ll i1;in;i){ll xpos[i];if(p[x]x)p[x]r[x];else p[x]l[x];l[r[x]]l[x];r[l[x]]r[x];}for(ll in-1;i1;i--){ll xpos[i];f[x]f[p[x]]abs(p[x]-x);}for(ll i1;in;i)printf(%lld\n,f[i]);return 0;
}
