[LOJ 2039] 「SHOI2015」激光发生器
链接
题解
分为两个部分
第一个是求直线之间的交点找到第一个触碰到的镜面
第二个是求直线经过镜面反射之后的出射光线
第一个很好做，第二个就是将入射光线旋转，注意旋转后在哪一面（可能到镜面背后去）
代码
// Copyright lzt
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i, j, k) for (register int i = (int)(j); i <= (int)(k); i++)
#define rrep(i, j, k) for (register int i = (int)(j); i >= (int)(k); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = 10 * x + ch - '0';
ch = getchar();
}
return x * f;
}
const int maxn = 110;
const double eps = 1e-8;
const double pi = acos(-1);
struct Point {
double x, y;
Point(double _x = 0, double _y = 0) {
x = _x; y = _y;
}
Point operator + (const Point &b) const {
return (Point){x + b.x, y + b.y};
}
Point operator - (const Point &b) const {
return (Point){x - b.x, y - b.y};
}
Point operator * (const double &b) const {
return (Point){x * b, y * b};
}
};
typedef Point Vector;
struct Line {
Point x; Vector y;
Line() {}
Line(Point _x, Vector _y) {
x = _x; y = _y;
}
};
struct LLL {
Point p1, p2;
double a, b;
} A[maxn];
double Dot(const Vector &a, const Vector &b) {
return a.x * b.x + a.y * b.y;
}
double Cross(const Vector &a, const Vector &b) {
return a.x * b.y - a.y * b.x;
}
double Len(const Vector &a) {
return sqrt(Dot(a, a));
}
int dcmp(double x) {
return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
}
Point intersect(const Line &a, const Line &b) {
Vector v = a.x - b.x;
double t = Cross(b.y, v) / Cross(a.y, b.y);
return a.x + a.y * t;
}
double Angle(const Vector &a, const Vector &b) {
return acos(Dot(a, b) / Len(a) / Len(b));
}
bool onseg(const Point &p, const Point &a, const Point &b) {
return dcmp(Dot(a - p, b - p)) <= 0 && dcmp(Cross(a - p, a - p)) == 0;
}
Vector rotate(const Vector &a, double b) {
return (Vector){a.x * cos(b) - a.y * sin(b), a.y * cos(b) + a.x * sin(b)};
}
double X, Y, dx, dy;
int n;
void work() {
X = read(), Y = read(), dx = read(), dy = read();
n = read();
rep(i, 1, n) {
A[i].p1.x = read(); A[i].p1.y = read();
A[i].p2.x = read(); A[i].p2.y = read();
A[i].a = read(), A[i].b = read();
}
Point nw = (Point){X, Y};
Vector v = (Vector){dx, dy};
rep(_, 1, 10) {
int ind = 0; double nwdis = 1e9;
rep(i, 1, n) {
if (dcmp(Cross(A[i].p1 - A[i].p2, v)) == 0) continue;
Point p = intersect(Line(A[i].p1, A[i].p2 - A[i].p1), Line(nw, v));
if (onseg(p, A[i].p1, A[i].p2) && dcmp(Dot(v, p - nw)) > 0) {
double dis = Len(p - nw);
if (dis < nwdis) nwdis = dis, ind = i;
}
}
if (!ind) {
if (_ == 1) puts("NONE");
break;
}
printf("%d ", ind);
nw = intersect(Line(A[ind].p1, A[ind].p2 - A[ind].p1), Line(nw, v));
if (dcmp(Dot(A[ind].p1 - A[ind].p2, v)) == 0) v = v * (-1);
else {
Vector nwv;
if (dcmp(Dot(A[ind].p1 - A[ind].p2, v)) > 0) nwv = A[ind].p1 - A[ind].p2;
else nwv = A[ind].p2 - A[ind].p1;
double alpha = pi / 2 - Angle(nwv, v);
if (dcmp(Cross(nwv, v)) > 0) v = rotate(nwv, alpha * A[ind].a / A[ind].b - pi / 2);
else v = rotate(nwv, pi / 2 - alpha * A[ind].a / A[ind].b);
}
}
}
int main() {
#ifdef LZT
freopen("in", "r", stdin);
#endif
work();
#ifdef LZT
Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
}