严格来说,这就是一道模拟题。

大概思路就是找到第一条碰到的线段,之后旋转角度就好了。

只是计算几何题全忘了而已(或者根本没学)。

$x_0= |R|*\operatorname{cos}\alpha,y_0= |R|*\operatorname{sin}\alpha$

$\begin{aligned}x_1&= |R|*\operatorname{cos}(\alpha+\beta)\\&=|R|*(\operatorname{cos}\alpha\operatorname{cos}\beta-\operatorname{sin}\alpha\operatorname{sin}\beta)\\&=x_0\operatorname{cos}\beta-y_0\operatorname{sin}\beta\end{aligned}$

$\begin{aligned}y_1&= |R|*\operatorname{sin}(\alpha+\beta)\\&=|R|*(\operatorname{sin}\alpha\operatorname{cos}\beta+\operatorname{cos}\alpha\operatorname{sin}\beta)\\&=x_0\operatorname{sin}\beta+y_0\operatorname{cos}\beta\end{aligned}$

只要把$\alpha,\beta$角算出来就可以实现旋转了。

找第一条碰到的线段的话,可以$O(n)$扫。

根据题意,平行的不要,可以表示成叉积为$0$(叉积$<0$,前相对于后在左边,反之在右边,这个是惯用操作?)。

如果不是平行的,把交点$t$求出来,求交点时就记住,上面1 3 4 3,下面4 3 2 1($p_i$)。

考虑交点不可行的情况:

  1. 与当前射线反向,即射线不会经过$t$,而直线会。
  2. 交点$t$没有落在线段上。

这里得要引进点积

点积的值$>0$,即夹角$0\le\theta<\frac{\pi}{2}$

点积的值$=0$,即夹角$\theta=\frac{\pi}{2}$

点积的值$<0$,即夹角$\frac{\pi}{2}<\theta\le \pi$

因此情况$1$无非就是$\theta =0,\theta=\pi$两种情况,用一下点积也行,讨论一下也行。

情况$2$,也是类似的,不保险的话,可以再用下叉积。

第一条碰到的线段,即为距离射线起点最短的线段。

求出来之后,可以进一步简化,要求$\alpha$在$(0,\frac{\pi}{2})$下,即射线与线段的夹角。

之后就是求角度,旋转的问题,上文已经提及。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define eps 1e-8
using namespace std;
const int N=105;
inline int cmp(double x){return fabs(x)<eps?0:(x<0?-1:1);}
struct node
{
    double x,y;
    node(double x=0,double y=0):x(x),y(y){}
    node operator +(const node a)const{return node(x+a.x,y+a.y);}
    node operator -(const node a)const{return node(x-a.x,y-a.y);}
    node operator *(const double a)const{return node(x*a,y*a);}
    node operator /(const double a)const{return node(x/a,y/a);}
    node rotate(double ang){return node(x*cos(ang)-y*sin(ang),x*sin(ang)+y*cos(ang));}
    bool operator <(const node a)const{return fabs(x-a.x)<eps?y<a.y:x<a.x;}
};
struct data{node p1,p2;int a,b;}a[N];
inline double dot(const node &p1,const node &p2){return p1.x*p2.x+p1.y*p2.y;}
double length(const node &p){return sqrt(dot(p,p));}
double angle(const node &p1,const node &p2){return acos(dot(p1,p2)/(length(p1)*length(p2)));}
inline double cross(const node &p1,const node &p2){return p1.x*p2.y-p1.y*p2.x;}
node jd(node p1,node p2,node p3,node p4){return p1+(p2-p1)*cross(p1-p3,p4-p3)/cross(p4-p3,p2-p1);}
bool pd(node t,node p1,node p2){return fabs(cross(t-p1,t-p2))<eps&&cmp(dot(t-p1,t-p2))<0;}//情况2
int main()
{
    int x,y,dx,dy,n;scanf("%d%d%d%d%d",&x,&y,&dx,&dy,&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf%d%d",&a[i].p1.x,&a[i].p1.y,&a[i].p2.x,&a[i].p2.y,&a[i].a,&a[i].b);
    node p(x,y),v(dx,dy);int flag=1;
    for(int T=1;T<=10;T++)
    {
        double mn=1e10;int id=0;
        for(int i=1;i<=n;i++)
            if(fabs(cross(a[i].p2-a[i].p1,v))>eps)
            {
                node t=jd(p,p+v,a[i].p1,a[i].p2);
                if(pd(t,a[i].p1,a[i].p2)&&cmp(dot(v,t-p))>0)
                {
                    double dis=length(t-p);
                    if(dis<mn)mn=dis,id=i;
                }
            }
        if(!id)break;
        p=jd(p,p+v,a[id].p1,a[id].p2);
        if(cmp(dot(v,a[id].p2-a[id].p1))==0)v=v*-1;
        else
        {
            node t=a[id].p2-a[id].p1;
            if(cmp(dot(t,v))<0)t=node(0,0)-t;
            double ang=acos(-1)/2-angle(t,v);
            int bt=cmp(cross(t,v));//判断t,v方向,之后利用t旋转。
            v=t.rotate(bt*(ang*a[id].a/a[id].b-acos(-1)/2));//t需要逆时针旋转多少 
        }
        printf("%d ",id);flag=0;
    }
    if(flag)puts("NONE");
    else puts("");
    return 0;
}