2020牛客寒假算法基础集训营1 umi和弓道
https://ac.nowcoder.com/acm/contest/3002/C
题意
在一个无限大的平面中，一个人站在 这个坐标。
有 n 个靶子，第 i 个靶子的坐标是
在 x 轴或 y 轴上放置一块挡板来挡住弓箭的轨迹，使可以射中的靶子数量不超过 k 个，挡板的最短长度是多少？
注：
弓箭的轨迹是起点为 这个坐标，长度无穷大的射线。
挡板不能弯折，起始和终点必须在同一坐标轴上。
题解
如果靶子坐标的象限与弓箭起点相同，那么挡板肯定挡不住。如果不同，那就记录弓箭轨迹与 x，y 轴的交点，进行双指针维护最小值。
代码
#include<bits/stdc++.h>
using namespace std;
double xx,yy;
int n,k;
vector<double> vx,vy;
int main()
{
double x,y,ans=1e18;
int i,l,r;
scanf("%lf%lf%d%d",&xx,&yy,&n,&k);
for(i=0;i<n;i++)
{
scanf("%lf%lf",&x,&y);
if(x*xx<0) vy.push_back(y-(yy-y)/(xx-x)*x);
if(y*yy<0) vx.push_back(x-(xx-x)/(yy-y)*y);
}
sort(vx.begin(),vx.end());
sort(vy.begin(),vy.end());
if(vx.size()>=n-k)
{
l=0;r=n-k-1;
while(r<vx.size())
{
ans=min(ans,vx[r]-vx[l]);
r++;
l++;
}
}
if(vy.size()>=n-k)
{
l=0;r=n-k-1;
while(r<vy.size())
{
ans=min(ans,vy[r]-vy[l]);
r++;
l++;
}
}
if(ans==1e18) printf("-1");
else printf("%.8lf",ans);
system("pause");
return 0;
}