読者です 読者をやめる 読者になる 読者になる

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