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; }