umi和弓道 计算几何 详解

题目链接：https://ac.nowcoder.com/acm/contest/3002/C
题目：


思路：
和（x0,y0） ，在同一象限的无法挡住
要射中k个，只用挡住n−k个即可
1，对于每个靶子与（x0,y0）的连线交于y 轴时，把这一点当住即挡住了一个靶子，把所有交在y 轴的点统计排序，找到最近的n−k 个点，即最小长度
2，每个靶子与（x0,y0）的连线交于x 轴时，同理找一个最小值，结果取最小即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int maxn=1e5+5;
vector<double>v1,v2;
int main()
{
    double x0,y0;
    int n,k;
    scanf("%lf%lf",&x0,&y0);
    scanf("%d%d",&n,&k);
    k=n-k;
    for(int i=1;i<=n;i++)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        if(y*y0<0)    ///板子在x轴
        {
            double xx=x0-y0*(x-x0)/(y-y0);
            v1.push_back(xx);
        }
        if(x*x0<0)  ///板子在y轴
        {
            double yy=y0-x0*(y-y0)/(x-x0);
            v2.push_back(yy);
        }
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    int len1=v1.size();
    int len2=v2.size();
    if(len1<k&&len2<k)
    {
        printf("-1\n");
    }
    else
    {
        double ans=1e18;    ///注意double的最大上限

        for(int i=k-1;i<v1.size();i++)
        {
            ans=min(ans,v1[i]-v1[i-k+1]);
        }

        for(int i=k-1;i<v2.size();i++)
        {
            ans=min(ans,v2[i]-v2[i-k+1]);
        }
        printf("%.8lf\n",ans);
    }
}