n个月没更了，现在学的东西很难，掌握不好，不敢更！

这个题目既不超范围又足够难想，反正我没想出来，很好的题目！

我发现noi.ac上的题目很不错！！！

-------------------------------------------------------------------------------------------------------------------

小z告诉小w了这样一道送分题。

在数轴上有n个小人，第ii个人现在在pi位置，速度是vi（速度的正负代表不同的方向）。如果某一时刻两个人在同一位置，那么就会发生碰撞。

如果现在小j可以使用能力，使得其中kk个人凭空消失，那么最多会有多长时间内，没有任何两个人会碰撞呢？

输入格式

一行两个整数 n和k。

接下来 n行，每行两个整数pi,vi，表示每个人的初始位置和速度。

输出格式

如果时间是无限长，输出Forever, 否则输出一个实数表示答案，答案误差小于10^−3即可。

样例一

input

4 1 1 1 3 -1 5 2 7 -2

output

1.00

样例二

input

4 2 1 1 3 -1 5 2 7 -2

output

Forever

数据范围和约定

本题采用捆绑测试，对于全部数据，1≤k≤n≤10^5;|pi|,|vi|≤10^9.

_________________________________________________________________________________________

碰撞，可以选择让他消失。肯定先碰撞就让他消失。同时维护那么多点的位置？肯定是按照时间进行二分。消失如何处理？那就让他不消失，位置交换以后就是逆序，只要求最长上升子序列就好了！！

说起来简单，想的时候真的想不到！！！

所以正解就是二分答案+最长上升子序列。

注意刚开始的预处理！！！

1 #include
      
        2 using namespace std; 3 const int maxn=100005; 4 int n,k; 5 struct node 6 { 7     int v,p; 8 }pt[maxn]; 9 bool cmp(node a,node b)10 {11     if(a.p
       
        b.v)return 1;13     return 0;14 }15 int f[maxn];16 long double pos[maxn],low[maxn];17 bool pd(long double x)18 {19     for(int i=1;i<=n;++i)pos[i]=pt[i].p+pt[i].v*x,low[i]=3e9;20     int ans=1;21     low[1]=pos[1];22     for(int i=2;i<=n;++i)23     {24         if(low[ans]
        
         0.0000001)43     {44         long double mid=(l+r)/2;45         if(pd(mid))l=ans=mid;46         else r=mid;47     }48     if(ans>2.9e9)printf("Forever");49     else printf("%.6lf",(double)ans);50     return 0;51 }