GDOI2014模拟pty爬山（mountain）

pty爬山（mountain）

在Pty学校附近，有一座名之为岳之麓的高山。Pty很喜欢和（哔——）一起爬山。
山的平面模型如下：
山由一个顶点集：A1,A2…An给定，保证Ai的x单调递增。我们将Ai和Ai+1之间连上线段，表示山的某一段。如下图所示：
GDOI2014模拟pty爬山（mountain）
Pty想要爬到这座山的最高的顶点，当两个顶点的高度相同时，我们认为x比较大的顶点要高一些。Pty不是盲人，所以他将会在爬山时采取一些策略，使得他能够尽量快的到达最高的顶点。
Pty从初始的顶点出发，往左右看去，他将朝他能够看到的最高的顶点方向走去。当走到每一个顶点时，他都会重新观察，如果这时看到的顶点比之前看到的顶点还要高，那么他将选择此时看到的顶点走去，直到他到达最高点为止。如果顶点A能够看到顶点B，则线段AB没有严格穿过山的内部。
例如上图中：Pty从A4点出发。他能够看到的最高点是A6，所以他将会向右侧走去。当他到达A5号点时，能够看到A1点比A6点更高，所以他会调转方向，向左侧走去。由于A1是最高的顶点，所以他将一直往左侧走，直到到达A1为止。
Pty想知道从每一个顶点出发，分别需要走过多少段才能到达最高点。例如上图中从A4出发需要走过5段才能到达最高点。

输入格式：

第一行输入n，表示n个顶点。
接下来n行，每行两个整数xi, yi，表示第i个顶点的坐标。
输入保证xi单调递增。

输出格式：

输出共n行：第i行表示从第i个顶点出发走到最高点需要经过多少段。

样例输入：

样例输出：

数据范围：

30%的数据满足：n<= 100
60%的数据满足：n <= 50000
100%的数据满足：n<=200000, xi<=10^6, yi <= 10^6

i一定能看见i−1

i如果看不见l[i−1],那么一定看不见1~l[i−1]

i如果看得见l[i−1]且看不见l[l[i−1]]，那么l[i]=l[i−1]

所以可以用动态规划在O(n)内求出i点向左、向右能看到的最高点。

然后再处理出每个点出发时能看到的最高点，将它按照y与x从小到大排序

按照排序后的顺序，高度从低到高的点依次做。这个点该往哪边走，双向链表中对应方向上与之相邻的点就是要找的点，然后把做过的点删掉即可。（妙！

发现形成了一棵以最高点为根的树，dfs求出答案即可。

 #include<cstdio>
 #include<cstring>
 #include<iostream>
 #include<algorithm>
 using namespace std;
 ;
 struct node{
     int next,to;
 }edge[N];
 struct no{
     int y,z,to;
 }a[N];
 ,L[N],R[N],f[N];
 inline void del(int x)
 {
     R[L[x]]=R[x];
     L[R[x]]=L[x];
 }
 inline bool see(int a,int b,int c)//a>b>c
 {
     double s=(0.0+y[a]-y[c])/(x[a]-x[c]+0.0);
     s=s*(x[b]-x[c])+y[c];
     if(y[b]<=s) return true;
     else return false;
 }
 inline void unite(int x,int y)
 {
     s++;
     edge[s].to=y;
     edge[s].next=head[x];
     head[x]=s;
 }
 inline void dfs(int x,int dis)
 {
     f[x]=dis;
     for(int i=head[x];i;i=edge[i].next) dfs(edge[i].to,dis+abs(x-edge[i].to));
 }
 inline ?x:-x);}
 inline bool cmp(no a,no b){if(a.y!=b.y) return a.y<b.y;return a.to<b.to;}
 int main()
 {
     ,rec,p,et;
     scanf("%d",&n);
     ;i<=n;i++)
     {
         scanf("%d%d",&x[i],&y[i]);
         if(mx<=y[i]){mx=y[i];rec=i;}
     }
     ;i<=n;i++)
     {
         l[i]=i-;
         ) l[i]=l[l[i]];
     }
     r[n]=n+;
     ;i>=;i--)
     {
         r[i]=i+;
         while(y[r[i]]<=y[r[r[i]]]&&see(r[r[i]],r[i],i)&&r[i]!=n) r[i]=r[r[i]];
     }
     ;i<=n;i++)
     {
         R[i]=i+;
         L[i]=i-;
         a[i].z=i;
         if(y[r[i]]>=y[l[i]]) a[i].to=r[i];
         else a[i].to=l[i];
         a[i].y=y[a[i].to];
     }
     a[rec].y=;
     sort(a+,a+n+,cmp);
     ;i<n;i++)
     {
         p=a[i].z;
         if(a[i].to<p) et=L[p];
         else et=R[p];
         unite(et,p);
         del(p);
     }
     dfs(rec,);
     ;i<=n;i++) printf("%d\n",f[i]);
     ;
 }

秒客网