5163: 第k大斜率
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 15 Solved: 4
[Submit][Status][Discuss]
Description
在平面直角坐标系上，有n个不同的点。任意两个不同的点确定了一条直线。请求出所有斜率存在的直线按斜率从
大到小排序后，第k条直线的斜率为多少。为了避免精度误差，请输出斜率向下取整后的结果。（例如：[1.5]=1，
[-1.5]=-2）
Input
第一行，包含两个正整数n和k。
接下来n行，每行包含两个整数xi,yi，表示每个点的横纵坐标。
1 ≤ n≤ 100000 ， k ≤ n ， |xi|, |yi| ≤ 10^8
Output
输出一行，包含一个整数，表示第k小的斜率向下取整的结果。
Sample Input
4 1
-1 -1
2 1
3 3
1 4
-1 -1
2 1
3 3
1 4
Sample Output
2
估计正解对于大家来说都很简单。。。但是这题的题面太坑了。
首先不要轻易相信上述的题面，让我先来讲讲我的做题过程。。。。。
1.x坐标相同的是不是算斜率无穷大啊？？？？一开始我这么想，后来发现x坐标的斜率不算之后能多撑1s多再WA，这说明x坐标相同的不能算。。。
这个还是最不坑啊，，，，
2.你们发没发现题目的OUTPUT里写的是第k小，但是通过观察样例和题目描述发现其实是第k大。。。
这个也还好，毕竟写反了可以看样例看出来。。。但是最后这个。。。
3.题目里说k<=n，我一开始还真信了hhhh，后来一直WA一直WA终于想到了n个点最多有n*(n-1)/2条可以计算斜率的直线，所以k开成long long还是好一点。。。
(然后开成long long就A了hhhh，我TM要打死出题人这题面真是没谁了，估计还要误导好多人hhhh)
#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
int l,r,mid,ans;
const int inf=1000000000;
int px[maxn],ky;
struct node{
int x,y;
ll tmp; bool operator <(const node& u)const{
return tmp==u.tmp?x<u.x:tmp<u.tmp;
}
}a[maxn];
int n,m,f[maxn];
ll k; inline int query(int x){
int an=0;
for(;x;x-=x&-x) an+=f[x];
return an;
} inline void update(int x,int y){
for(;x<=ky;x+=x&-x) f[x]+=y;
} inline ll calc(){
ll an=0;
memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) a[i].tmp=(ll)a[i].y-mid*(ll)px[a[i].x]; sort(a+1,a+n+1); for(int i=1;i<=n;i++){
an+=(ll)query(a[i].x-1);
update(a[i].x,1);
} return an;
} int main(){
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
px[i]=a[i].x;
}
sort(px+1,px+n+1);
ky=unique(px+1,px+n+1)-px-1;
for(int i=1;i<=n;i++) a[i].x=lower_bound(px+1,px+ky+1,a[i].x)-px; l=-inf,r=inf;
while(l<=r){
mid=l+r>>1;
if(calc()>=k) ans=mid,l=mid+1;
else r=mid-1;
} printf("%d\n",ans);
return 0;
}