计算几何

tim
通过计算面积比例得出两直线的交点位置

double area(double x1,double y1,double x2,double y2,double x3,double y3){
    double s=0.5*((x1*y2-x2*y1)+(x2*y3-x3*y2)+(x3*y1-x1*y3));
    return s;
}//三点计算三角形面积公式A1(X1,Y1),A2(X2,Y2),A3(X3,Y3)逆时针输入
//面积结果为负时A3在A1A2的右边(A1-〉A2-〉A3实际为顺时针)

#include<bits/stdc++.h>
using namespace std;
int n, m;
int xs, ys, xt, yt;
double x[1010], y[1010];
vector<double> kk[1010];
double area(double x1,double y1,double x2,double y2,double x3,double y3){
    double s=0.5*((x1*y2-x2*y1)+(x2*y3-x3*y2)+(x3*y1-x1*y3));
    return s;
}
int main(){
    scanf("%d %d",&n,&m);
    scanf("%d %d %d %d",&xs,&ys,&xt,&yt);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            double k=area(x[i],y[i],xs,ys,x[j],y[j]);//逆时针输入
            k/=k+area(x[i],y[i],x[j],y[j],xt,yt);//
            if(k>=0&&k<=1){//在线段上
                kk[i].push_back(k);
                kk[j].push_back(k);
            }
        }
    }
    while(m--){
        int ii, cnt;
        scanf("%d %d",&ii,&cnt);
        sort(kk[ii].begin(),kk[ii].end());
        if(cnt>kk[ii].size())puts("-1");
        else 
            printf("%0.6lf %0.6lf\n",kk[ii][cnt-1]*(xt-xs)+xs,
                   kk[ii][cnt-1]*(yt-ys)+ys);
    }
    return 0;
}