JAG夏合宿2014 3日目 H - Points and Lines
問題文
http://jag2014autumn.contest.atcoder.jp/tasks/icpc2014autumn_h
感想
問題文には左優先で計算すると書いてあるが、自分は初めは、順序は任意に決定されるかつ幾何的制約を満たすものが最終的な解になるのでは、と思ってしまった。以下の参考問題の影響かもしれない。
参考問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255
#include <bits/stdc++.h> using namespace std; typedef complex<double> P; typedef pair<P, P> L; const double EPS = 1e-8; #define F first #define S second double dot(const P& a, const P& b) { return real(conj(a)*b); } double cross(const P& a, const P& b) { return imag(conj(a)*b); } P proj(const P& p, const L& l) { P k = dot(p-l.F, l.F-l.S) / norm(l.F - l.S); return l.F + k*(l.F - l.S); } P reflect(const P& p, const L& l) { return proj(p, l) * 2. - p; } P crossPoint(const L& a, const L& b) { P p1 = cross(a.S - a.F, b.S - b.F); P p2 = cross(a.S - a.F, a.S - b.F); return b.F + p2 / p1 * (b.S - b.F); } string str; enum { LINE, POINT, ERROR }; struct PorL { int isLine; L c; PorL(int is=ERROR, L c=L()) : isLine(is), c(c) {} }; int getNum(int l, int r) { char chs[100]; for(int i=l; i<r; i++) { chs[i-l] = str[i]; } chs[r-l] = 0; return atoi(chs); } PorL getPoint(int l, int r) { // Point for(int i=l; i<r; i++) { if(str[i] == ',') { int lhs = getNum(l, i); int rhs = getNum(i+1, r); return PorL(POINT, L(P(lhs, rhs), P(-1.,-1.))); } } assert(false); } PorL calc(int l, int r) { int idx = -1; int par = 0; bool pflag = false; // reverse for(int i=r-1; i>=l; i--) { if(i < r-1 && par == 0) { idx = i; break; } if(str[i] == ')') par++, pflag = true; // reverse count if(str[i] == '(') par--, pflag = true; } if(!pflag) { return getPoint(l, r); } // binary operation if(idx == -1) { return calc(l+1, r-1); } else if(str[idx] == '@') { PorL lhs(calc(l, idx)); PorL rhs(calc(idx+1, r)); PorL res; if(lhs.isLine == LINE && rhs.isLine == LINE) { res.c.F = crossPoint(lhs.c, rhs.c); res.c.S = P(-1.,-1.); res.isLine = POINT; } else if((lhs.isLine == POINT && rhs.isLine == LINE)) { res.c.F = reflect(lhs.c.F, rhs.c); res.c.S = P(-1.,-1.); res.isLine = POINT; } else if(lhs.isLine == LINE && rhs.isLine == POINT) { res.c.F = reflect(rhs.c.F, lhs.c); res.c.S = P(-1.,-1.); res.isLine = POINT; } else if(lhs.isLine == POINT && rhs.isLine == POINT) { res.c = L(lhs.c.F, rhs.c.F); res.isLine = LINE; } else { assert(false); } return res; } assert(false); return PorL(); } int main() { while(cin >> str) { if(str == "#") break; PorL ans(calc(0, str.size())); assert(ans.isLine == POINT); printf("%.8f %.8f\n", ans.c.F.real(), ans.c.F.imag()); } return 0; }