自动搬运

查看原文

来自洛谷，原作者为

	81179332_ 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:59:22，当前版本为作者最后更新于2020-02-23 20:44:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

$\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");
}