严格来说,这就是一道模拟题。
大概思路就是找到第一条碰到的线段,之后旋转角度就好了。
只是计算几何题全忘了而已(或者根本没学)。
$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$)。
考虑交点不可行的情况:
- 与当前射线反向,即射线不会经过$t$,而直线会。
- 交点$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;
}
0 条评论