https://ac.nowcoder.com/acm/contest/12548/I

从一条直线一侧观察上面的点，求平面上的某一点与其他点相对位置关系相反次数达到某一值时在直线的最左侧位置

二分出起点向量方向向量大小倍率(0,1],判断条件为这一点与其余点叉积与刚开始时异号次数，大于等于k时候条件满足，缩小倍率。若最后倍率大于1则无解。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;
typedef pair<double, double> P;
const double eps = 1e-10,INF = 1e7;
const int N = 1e4+10;

int n,m;
P s,t;
P res[N],p[N],q[N];
int h,k;

int sign(double x){
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    return 1;
}

int dcmp(double x,double y){
    if(fabs(x-y)<eps) return 0;
    if(x<y) return -1;
    return 1;
}

P operator - (P a,P b){
    return {a.x-b.x,a.y-b.y};
}

P operator + (P a,P b){
    return {a.x+b.x,a.y+b.y};
}

P operator * (P a,double t){
    return {a.x*t,a.y*t};
}

P operator / (P a,double t){
    return {a.x/t,a.y/t};
}

double operator & (P a,P b){
    return a.x*b.x+a.y*b.y;
}

double operator * (P a,P b){
    return a.x*b.y-a.y*b.x;
}

bool check(double x){
    auto o=s+(t-s)*x;
    int sum=0;
    for(int i=1;i<=n;i++){
        if(i==h) continue;
        sum+=sign(((p[i]-s)*(p[h]-s))*((p[i]-o)*(p[h]-o)))<0;
    }
    return sum>=k;
}

int main(){
    cin>>n>>m;
    cin>>s.x>>s.y>>t.x>>t.y;
    for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y,q[i]=p[i];
    while(m--){
        int cnt=0;
        cin>>h>>k;
        double l=0,r=1.1;
        while(r-l>1e-10){
            double mid=(l+r)/2;
            if(check(mid)) r=mid;
            else l=mid;
        }
        if(dcmp(r,1.0)>0){
            puts("-1");
            continue;
        }
        auto res=s+(t-s)*r;
        printf("%.10lf %.10lf\n",res.x,res.y);
    }


    return 0;
}