原题链接
题意：
车从( s x , s y )开往( e x , e y )，在车的同一侧有n个风车，q次询问，每次询问第h个点对于其他点的位置变化的第k次的点。
思路：
题意有点抽象，模拟一下样例就很好懂了。
第二个样例问的是3号点第二个变化的位置点。
从s ss向e ee走，当车在[ s , A ]区间时，在车的视角看，1 , 2 , 4都在3的左边。
当车在[ A , B ]区间时，4变成了在3的右边，而1 , 2都在3的左边，所以第一个变化的点是4，第一个变化的位置是A.
当车在[ B , C ]区间时，2也变成了在3的右边，这时候2 , 4都在3 的右边，1在3的左边，所以第二个变化的点是2，第二个变化的位置是B.
当车在[ C , + 00 ]区间时，1也变成了在3的右边，这时候1 , 2 , 4都在3的右边，所以第三个变化的点是1，第二个变化的位置是C.
思路就是求每个点跟询问点所组成的直线和直线( s , e )的交点，按照交点到起点s的距离从小到大排序，第k个的交点坐标就是答案。
要注意只有交点在[ s , e ]时才是有效的。
运气比较好，找的板子没有被卡精度。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const double eps = 1e-8; const int maxn=1e6+100; int n,m; const double epsi=1e-10; struct Point { double x,y; Point(double _x=0,double _y=0):x(_x),y(_y){} Point operator -(const Point &op) const { return Point(x-op.x,y-op.y); } double operator ^(const Point &op) const { return x*op.y-y*op.x; } }; inline int sign(const double &x) { if(x>epsi) return 1; if(x<-epsi) return -1; return 0; } inline double sqr( const double &x) { return x*x; } inline double dis(const Point &p1,const Point &p2) { return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y)); } inline double mul(const Point &p0,const Point &p1,const Point &p2) { return (p1-p0)^(p2-p0); } inline int cross(const Point &p1,const Point &p2,const Point &p3,const Point &p4,Point &p) { double a1=mul(p1,p2,p3),a2=mul(p1,p2,p4); if(sign(a1)==0&&sign(a2)==0) return 2;//重叠 if(sign(a1-a2)==0) return 0;//平行 p.x=(a2*p3.x-a1*p4.x)/(a2-a1); p.y=(a2*p3.y-a1*p4.y)/(a2-a1); return 1;//相交 } Point a[1100],s,e; struct node{ double x,y,d; }b[1100]; bool cmp(node a,node b){ return a.d<b.d; } int main() { n=read,m=read; scanf("%lf%lf%lf%lf",&s.x,&s.y,&e.x,&e.y); rep(i,1,n){ scanf("%lf%lf",&a[i].x,&a[i].y); } double FUCK=dis(s,e); rep(i,1,m){ int idx=0,h=read,k=read; rep(j,1,n){ if(j==h) continue; Point t; int flag=cross(a[h],a[j],s,e,t); if(flag&&dis(t,s)<=FUCK&&dis(t,e)<=FUCK){ b[++idx]={t.x,t.y,dis(t,s)}; } } ///cout<<i<<"*******"<<idx<<endl; if(idx<k) puts("-1"); else{ sort(b+1,b+1+idx,cmp); printf("%.10lf %.10lf\n",b[k].x,b[k].y); } } return 0; }
