题解 P4361 【[SHOI2015]激光发生器】

· · 题解

这里给出向量旋转公式的推导过程。

\cos A=\dfrac{x_0}{|R|},\sin A=\dfrac{y_0}{|R|} x_1=|R|\cdot \cos(A+B) \ \ \ \ \ =|R|\cdot (\cos A\cos B-\sin A\sin B) \ \ \ \ \ =|R|\cdot (\dfrac{x_0}{|R|}\cos B-\dfrac{y_0}{|R|}\sin B) \ \ \ \ \ =x_0\cos B-y_0\sin B y_1=|R|\cdot \sin(A+B) \ \ \ \ \ =|R|\cdot (\sin A\cos B+\cos A\sin B) \ \ \ \ \ =|R|\cdot (\dfrac{y_0}{|R|}\cos B+\dfrac{x_0}{|R|}\sin B) \ \ \ \ \ =x_0\sin B+y_0\cos B

所以向量 (x_0,y_0) 逆时针旋转角B后的向量为 (x_0\cos B-y_0\sin B,x_0\sin B+y_0\cos B)。

对于本题则直接模拟光线的反射过程即可。

#include<cstdio>
#include<cctype>
#include<cmath>
using namespace std;
//#define getchar() (SS == TT && (TT = (SS = BB) + fread(BB,1,1 << 15,stdin),TT == SS) ? EOF : *SS++)
char BB[1 << 15],*SS = BB,*TT = BB;
using namespace std;
inline int read()
{
    int x = 0,f = 1;
    char ch = getchar();
    for(;!isdigit(ch);ch = getchar())
        if(ch == '-')
            f = -1;
    for(;isdigit(ch);ch = getchar())
        x = x * 10 + (ch ^ 48);
    return x * f;
}
void print(long long x)
{
    if(x < 0)
        putchar('-'),x = -x;
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

const double eps = 1e-9,pi = acos(-1);
int dcmp(double x)
{
    if(fabs(x) < eps)
        return 0;
    return x < 0 ? -1 : 1;
}
struct point
{
    double x,y;

    void read()
    {
        x = ::read(),y = ::read();
    }
    point(double _x = 0,double _y = 0)
    {
        x = _x,y = _y;
    }
    friend point operator + (point szq,point yqy)
    {
        return point(szq.x + yqy.x,szq.y + yqy.y);
    }
    friend point operator - (point szq,point yqy)
    {
        return point(szq.x - yqy.x,szq.y - yqy.y);
    }
    friend point operator * (point szq,double yqy)
    {
        return point(szq.x * yqy,szq.y * yqy);
    }
    friend double operator * (point szq,point yqy)
    {
        return szq.x * yqy.x + szq.y * yqy.y;
    }
    friend double operator & (point szq,point yqy)
    {
        return szq.x * yqy.y - szq.y * yqy.x;
    }
    void rotate(double rad)
    {
        *this = point(x * cos(rad) - y * sin(rad),x * sin(rad) + y * cos(rad));
    }
    double lenth()
    {
        return sqrt((*this) * (*this));
    }
    bool onSeg(point szq,point yqy)
    {
        return dcmp((szq - *this) & (yqy - *this)) == 0 && dcmp((szq - *this) * (yqy - *this)) < 0;
    }
};
point intersection(point p,point v,point q,point w)
{
    return p + v * ((w & (p - q)) / (v & w));
}
double angle(point a,point b)
{
    return acos(a * b / a.lenth() / b.lenth());
}

const int N = 110;
int n;
struct Mirror
{
    point s,t;
    double a,b;
}a[N];
point p,d;
int main()
{
    p.read(),d.read();n = read();
    for(int i = 1;i <= n;i++)
        a[i].s.read(),a[i].t.read(),a[i].a = read(),a[i].b = read();
    bool fl = false;
    for(int T = 1;T <= 10;T++)
    {
        double minn = 1e200;
        int id = -1;
        for(int i = 1;i <= n;i++)
        {
            point v = a[i].t - a[i].s;
            if(dcmp(v & d))
            {
                point t = intersection(a[i].s,v,p,d);
                if(t.onSeg(a[i].s,a[i].t) && dcmp(d * (t - p)) > 0)
                {
                    double dis = (t - p).lenth();
                    if(dis < minn)
                        minn = dis,id = i;
                }
            }
        }
        if(!~id)
            break;
        point v = a[id].t - a[id].s;
        p = intersection(a[id].s,v,p,d);
        print(id),putchar(' ');
        fl = true;
        if(!dcmp(v * d))
        {
            d = d * -1;
            continue;
        }
        if(dcmp(d * v) < 0)
            v = v * -1;
        double alpha = pi / 2 - angle(v,d);
        alpha = pi / 2 - alpha * a[id].a / a[id].b;
        int bt = dcmp(d & v);
        v.rotate(bt * alpha);
        d = v;
    }
    if(!fl)
        puts("NONE");
}