[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

}

巴特西

[LOJ 2039] 「SHOI2015」激光发生器

[LOJ 2039] 「SHOI2015」激光发生器

链接

题解

代码

最新文章

热门文章