ferinの競プロ帳

競プロについてのメモ

AOJ2596 Points and Lines

問題ページ
Points and Lines | Aizu Online Judge

考えたこと

  • BNFがパッと目に入って明らかに構文解析
  • 幾何の操作がBNFの形で与えられるのでその結果を求める
  • 幾何の操作は2点から直線を作る操作とreflectionと直線の交点
  • 割と単純な操作でライブラリを貼ればいいのでここはできる
  • 構文解析パートで難しい点としてLL(1)でない
  • 1字先読みしたところで<line-factor>か<point-factor>かとかの区別がつかない
  • ここでJAG合宿2018day1Eを思い出すとpointとlineをまとめたくなる
  • pointとlineをまとめられればそもそも区別する必要がない
  • 適当な構造体を作り構造体が保持しているのがpointなのかlineなのかを変数typeで管理
  • こうすると@が来た時に左辺と右辺のtypeから@ですべき操作を把握できる
  • BNFのpointとlineの部分を以下のように書く
<pl> = <plf> | <pl>@<plf>
<plf> = (<pl>) | (<num>,<num>)
  • これはが左再帰なので除去する
<pl> = <plf><pl_tail>
<pl_tail> = @<pl><pl_tail> | empty

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

const double EPS = 1e-8;

using R = long double;
using P = complex<R>;
using L = pair<P,P>;
using G = vector<P>;
struct C {
  P c; R r;
  C() {}
  C(const P &a, const R &b) : c(a), r(b) {}
};
struct S : public L {
  S() {}
  S(const P &a, const P &b) : L(a,b) {}
};

inline int sgn(const R& r) { return (r>EPS) - (r<-EPS); }
inline R dot(const P& a, const P& b) {
  return real(a)*real(b) + imag(a)*imag(b);
}
inline R det(const P& a, const P& b) {
  return real(a)*imag(b) - imag(a)*real(b);
}
inline P vec(const L& l) {return l.second - l.first;}
namespace std {
    bool operator < (const P& a, const P& b) {
        return sgn(real(a-b)) ? real(a-b) < 0 : sgn(imag(a-b)) < 0;
    }
    bool operator == (const P& a, const P& b) {
        return sgn(real(a-b)) == 0 && sgn(imag(a-b)) == 0;
    }
  bool cmp_y (const P& a, const P& b) {
    return sgn(imag(a-b)) ? imag(a-b) < 0 : sgn(real(a-b)) < 0;
  }
}

// P,L,Sについて入力
inline istream& operator>>(istream& is, P& p) {
  R x, y;
  is >> x >> y;
  p = P(x, y);
  return is;
}
inline istream& operator>>(istream& is, L& l) {
  P a, b;
  is >> a >> b;
  l = L(a, b);
  return is;
}

// 射影
P inline projection(const L &l, const P &p) {
  R t = dot(p-l.first, l.first-l.second) / norm(l.first-l.second);
  return l.first + t*(l.first-l.second);
}
// 反射
P inline reflection(const L &l, const P &p) {
  return p + (R)2 * (projection(l, p) - p);
}

// 交差判定
template<bool strict=false> inline bool intersect(const L&l1, const L&l2) {
  if(strict) return sgn(det(vec(l1),vec(l2))) != 0;
  return sgn(det(vec(l1),vec(l2))) != 0 || l1 == l2;
}

// 交点 交差判定を先にすること!!!
inline P crosspoint(const L& l1, const L& l2) {
  R ratio = det(vec(l2), l2.first-l1.first)/det(vec(l2),vec(l1));
  return l1.first + vec(l1)*ratio;
}

struct node {
  int type;
  P p;
  L l;
};

node plf();
node pl_tail();
node pl();

string s;
int pos = 0;
int number() {
  int ret = 0;
  bool neg = false;
  if(s[pos] == '-') neg = true, pos++;
  while(isdigit(s[pos])) {
    ret *= 10;
    ret += s[pos] - '0';
    pos++;
  }
  if(neg) ret *= -1;
  return ret;
}

node plf() {
  node ret;
  pos++;
  if(s[pos] == '-' || isdigit(s[pos])) {
    int vl = number();
    pos++;
    int vr = number();
    ret.type = 0;
    ret.p = P(vl, vr);
  } else {
    ret = pl();
  }
  pos++;
  return ret;
}

node pl() {
  // plfを読む
  node ret = plf();
  // pl_tailを読む
  while(pos < s.size() && s[pos] != ')') {
    if(s[pos] == '@') {
      pos++;
      node tmp = plf();
      // ret = ret @ tmp
      if(ret.type == 0 && tmp.type == 0) {
        ret.type = 1;
        ret.l = L(ret.p, tmp.p);
      } else if(ret.type == 0 && tmp.type == 1) {
        P p = reflection(tmp.l, ret.p);
        ret.type = 0;
        ret.p = p;
      } else if(ret.type == 1 && tmp.type == 0) {
        P p = reflection(ret.l, tmp.p);
        ret.type = 0;
        ret.p = p;
      } else if(ret.type == 1 && tmp.type == 1) {
        P p = crosspoint(ret.l, tmp.l);
        ret.type = 0;
        ret.p = p;
      } else {
        assert(false);
      }
    } else {
      cout << "err" << pos << " " << s[pos] << endl;
      assert(false);
    }
  }
  return ret;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    cin >> s;
    if(s == "#") break;

    pos = 0;
    node ret = pl();
    cout << fixed << setprecision(15) << ret.p.real() << " " << ret.p.imag() << endl;
  }

  return 0;
}