UVa 604 - The Boggle Game

Accepted date: 2014-10-27
Ranking (as of 2014-10-27): 27 out of 445
Language: C++

/*
  UVa 604 - The Boggle Game

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_604_The_Boggle_Game.cpp
*/

#include <iostream>
#include <set>
#include <cstring>
using namespace std;

const int nr_rows = 4, nr_columns = 4;
const int nr_letters = 4;

char first_board[nr_rows][nr_columns], second_board[nr_rows][nr_columns];
bool visited[nr_rows][nr_columns];

struct pigewu {
  char s_[nr_letters + 1];

  bool operator<(const pigewu& p) const {return strcmp(s_, p.s_) < 0;}
};

inline bool is_vowel(char c)
{
  return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' || c == 'Y';
}

void boggle(int r, int c, int l, int vl, pigewu& p, char board[nr_rows][nr_columns],
  set<pigewu>& pigewus)
{
  const int nr_dirs = 8;
  const int dirs[nr_dirs][2] =
    {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

  p.s_[l++] = board[r][c];
  if (is_vowel(p.s_[l - 1]))
    vl++;
  visited[r][c] = true;
  if (l == nr_letters) {
    p.s_[nr_letters] = '\0';
    pigewus.insert(p);
  }
  else {
    for (int i = 0; i < nr_dirs; i++) {
      int nr = r + dirs[i][0], nc = c + dirs[i][1];
      if (nr < 0 || nr >= nr_rows || nc < 0 || nc >= nr_columns || visited[nr][nc])
        continue;
      bool vowel = is_vowel(board[nr][nc]);
      if (vl == 2 && vowel || l == 2 && vl == 0 && !vowel ||
        l == 3 && vl == 1 && !vowel)
        continue;
      boggle(nr, nc, l, vl, p, board, pigewus);
    }
  }
  visited[r][c] = false;
}

int main()
{
  bool printed = false;
  while (true) {
    char c;
    cin >> c;
    if (c == '#')
      break;
    cin.unget();
    if (printed)
      cout << endl;
    else
      printed = true;
    for (int r = 0; r < nr_rows; r++) {
      for (int c = 0; c < nr_columns; c++)
        cin >> first_board[r][c];
      for (int c = 0; c < nr_columns; c++)
        cin >> second_board[r][c];
    }
    pigewu p;
    set<pigewu> first_pigewus, second_pigewus;
    for (int r = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++) {
        memset(visited, 0, sizeof(visited));
        boggle(r, c, 0, 0, p, first_board, first_pigewus);
        memset(visited, 0, sizeof(visited));
        boggle(r, c, 0, 0, p, second_board, second_pigewus);
      }

    size_t nr_first_pigewus = first_pigewus.size(),
      nr_secont_pigewus = second_pigewus.size();
    bool found = false;
    if (nr_first_pigewus && nr_secont_pigewus) {
      if (nr_first_pigewus > nr_secont_pigewus) {
        for (set<pigewu>::const_iterator i = second_pigewus.begin(),
          e = second_pigewus.end(); i != e; ++i)
          if (first_pigewus.find(*i) != first_pigewus.end()) {
            found = true;
            cout << i->s_ << endl;
          }
      }
      else {
        for (set<pigewu>::const_iterator i = first_pigewus.begin(),
          e = first_pigewus.end(); i != e; ++i)
          if (second_pigewus.find(*i) != second_pigewus.end()) {
            found = true;
            cout << i->s_ << endl;
          }
      }
    }
    if (!found)
      cout << "There are no common words for this pair of boggle boards.\n";
  }
  return 0;
}

UVa 726 - Decode

Accepted date: 2014-10-24
Ranking (as of 2014-10-24): 101 out of 271
Language: C++

/*
  UVa 726 - Decode

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_726_Decode.cpp
*/

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

const int nr_letters = 26;

struct letter {
  int i_, f_;

  letter() {}

  bool operator<(const letter& l) {return (f_ != l.f_) ? f_ > l.f_ : i_ < l.i_;}
};

#ifdef DEBUG
void print_letter_freqs(const vector<letter>& freqs)
{
  for (int i = 0; i < nr_letters; i++)
    if (freqs[i].f_)
      cout << static_cast<char>(freqs[i].i_ + 'a') << ' ';
  cout << endl;
}
#endif

int main()
{
  vector<letter> known_freqs(nr_letters);
  vector<letter> encoded_freqs(nr_letters);
  for (int i = 0; i < nr_letters; i++) {
    known_freqs[i].i_ = encoded_freqs[i].i_ = i;
    known_freqs[i].f_ = encoded_freqs[i].f_ = 0;
  }
  vector<string> known;
  string s;
  while (true) {
    getline(cin, s);
    if (s.empty())
      break;
    known.push_back(s);
    for (const char* p = s.c_str(); *p; p++)
      if (isalpha(*p))
        known_freqs[tolower(*p) - 'a'].f_++;
  }
  vector<string> encoded;
  while (getline(cin, s)) {
    encoded.push_back(s);
    for (const char* p = s.c_str(); *p; p++)
      if (isalpha(*p))
        encoded_freqs[tolower(*p) - 'a'].f_++;
  }
  sort(known_freqs.begin(), known_freqs.end());
  sort(encoded_freqs.begin(), encoded_freqs.end());
#ifdef DEBUG
  print_letter_freqs(known_freqs);
  print_letter_freqs(encoded_freqs);
#endif
  vector<char> mappings(nr_letters);
  for (int i = 0; i < nr_letters; i++)
    mappings[encoded_freqs[i].i_] = 'a' + known_freqs[i].i_;
  for (size_t i = 0, n = encoded.size(); i < n; i++) {
    ostringstream oss;
    for (const char* p = encoded[i].c_str(); *p; p++)
      if (isupper(*p))
        oss << static_cast<char>(toupper(mappings[*p - 'A']));
      else if (islower(*p))
        oss << mappings[*p - 'a'];
      else
        oss << *p;
    cout << oss.str() << endl;
  }
  return 0;
}

UVa 962 - Taxicab Numbers

Accepted date: 2014-10-21
Ranking (as of 2014-10-21): 143 out of 358
Language: C++

/*
  UVa 962 - Taxicab Numbers

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_962_Taxicab_Numbers.cpp
*/

#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
  const int nr_cubes_max = 1000;
  const int n1_max = 1000000000, rg_max = 100000;
  vector<int> cubes(nr_cubes_max);
  for (int i = 1; i <= nr_cubes_max; i++)
    cubes[i - 1] = i * i * i;
  map<int, int> sums_of_cubes;
  for (int i = 0; i < nr_cubes_max; i++)
    for (int j = i; j < nr_cubes_max; j++) {
      int s = cubes[i] + cubes[j];
      if (s <= n1_max + rg_max) {
        pair<map<int, int>::iterator, bool> result =
          sums_of_cubes.insert(make_pair(s, 1));
        if (!result.second)
          result.first->second++;
      }
    }
  vector<int> taxicab_numbers;
  for (map<int, int>::const_iterator si = sums_of_cubes.begin(),
    se = sums_of_cubes.end(); si != se; ++si)
    if (si->second >= 2)
      taxicab_numbers.push_back(si->first);
#ifdef DEBUG
  printf("%d %d\n",
    taxicab_numbers.size(), taxicab_numbers[taxicab_numbers.size() - 1]);
#endif
  int n1, rg;
  while (scanf("%d %d", &n1, &rg) != EOF) {
    vector<int>::iterator li =
      lower_bound(taxicab_numbers.begin(), taxicab_numbers.end(), n1),
      ui = upper_bound(taxicab_numbers.begin(), taxicab_numbers.end(), n1 + rg);
    if (li == ui)
      puts("None");
    else {
      for (; ui != li; ++li)
        printf("%d\n", *li);
    }
  }
  return 0;
}

UVa 10389 - Subway

Accepted date: 2014-10-19
Ranking (as of 2014-10-20): 67 out of 381
Language: C++

/*
  UVa 10389 - Subway

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10389_Subway.cpp
*/

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <limits>
#include <cmath>
#include <cstdlib>
using namespace std;

struct point {
  int x_, y_;
  int sl_; // subway line number
  int ss_; // subway station number
};

double euclidean_distance(const point& a, const point& b)
{
  double dx = a.x_ - b.x_, dy = a.y_ - b.y_;
  return sqrt(dx * dx + dy * dy);
}

struct edge {
  int v_;
  double w_;
  edge() {}
  edge(int v, double w) : v_(v), w_(w) {}
};

struct distance_comparator {
  vector<double>& distances_;
  distance_comparator(vector<double>& distances) : distances_(distances) {}
  bool operator() (const int i, const int j) const {
    if (distances_[i] != distances_[j])
      return distances_[i] < distances_[j];
    else
      return i < j;
  }
};

int main()
{
  string line;
  istringstream iss;
  getline(cin, line);
  iss.str(line);
  int nr_cases;
  iss >> nr_cases;
  iss.clear();
  getline(cin, line); // skip a blank line
  while (nr_cases--) {
    getline(cin, line);
    iss.str(line);
    vector<point> points;
    point s, e;
    s.sl_ = 0; e.sl_ = 1; s.ss_ = e.ss_ = -1;
    iss >> s.x_ >> s.y_ >> e.x_ >> e.y_;
    points.push_back(s);
    points.push_back(e);
    iss.clear();
    for (int sl = 2; getline(cin, line) && !line.empty(); sl++) {
      iss.str(line);
      point p;
      p.sl_ = sl;
      for (int ss = 0; ; ss++) {
        iss >> p.x_ >> p.y_;
        if (p.x_ == -1)
          break;
        p.ss_ = ss;
        points.push_back(p);
      }
      iss.clear();
    }
    const double walk = 10000.0 / 60.0, subway = 40000.0 / 60.0;
    int n = static_cast<int>(points.size());
    vector< vector<edge> > edges(n);
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++) {
        double d;
        if (points[i].sl_ == points[j].sl_)  {
          // two points are on the same subway line
          if (abs(points[i].ss_ - points[j].ss_) == 1) {
            // station i and station j are adjacent
            d = euclidean_distance(points[i], points[j]) / subway;
            edges[i].push_back(edge(j, d));
            edges[j].push_back(edge(i, d));
          }
        }
//        else {
          d = euclidean_distance(points[i], points[j]) / walk;
          edges[i].push_back(edge(j, d));
          edges[j].push_back(edge(i, d));
//        }
      }

    // apply Dijkstra's shortest path
    vector<double> distances(n, numeric_limits<double>::max());
    vector<bool> visited(n, false);
    set<int, distance_comparator> pq(distances); // priority queue
    distances[0] = 0.0;
    pq.insert(0);
    while (!pq.empty()) {
      int u = *pq.begin();
      pq.erase(pq.begin());
      visited[u] = true;
      if (u == 1)
        break;
      const vector<edge>& es = edges[u];
      for (size_t i = 0, j = es.size(); i < j; i++) {
        const edge& e = es[i];
        if (!visited[e.v_] && distances[e.v_] > distances[u] + e.w_) {
          pq.erase(e.v_); // remove vt if it has already been in the queue
            // this must be done before updating distances[]
          distances[e.v_] = distances[u] + e.w_;
          pq.insert(e.v_);
        }
      }
    }
    cout << fixed << setprecision(0) << distances[1] << endl;
    if (nr_cases)
      cout << endl;
  }
  return 0;
}

UVa 10724 - Road Construction

Accepted date: 2014-10-17
Ranking (as of 2014-10-17): 80 out of 310
Language: C++

/*
  UVa 10724 - Road Construction

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10724_Road_Construction.cpp
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

const double infinite = numeric_limits<int>::max(),
  epsilon = numeric_limits<double>::epsilon();

struct point {
  double x_, y_;
};

double euclidean_distance(const point& a, const point& b)
{
  double dx = a.x_ - b.x_, dy = a.y_ - b.y_;
  return sqrt(dx * dx + dy * dy);
}

int main()
{
  while (true) {
    int N, M;
    cin >> N >> M;
    if (!N && !M)
      break;
    vector<point> points(N + 1);
    for (int i = 1; i <= N; i++)
      cin >> points[i].x_ >> points[i].y_;
    vector< vector<bool> > roads(N + 1, vector<bool>(N + 1, false));
    vector< vector<double> > matrix(N + 1, vector<double>(N + 1, infinite));
    for (int i = 1; i <= N; i++)
      matrix[i][i] = 0.0;
    while (M--) {
      int i, j;
      cin >> i >> j;
      roads[i][j] = roads[j][i] = true;
      matrix[i][j] = matrix[j][i] = euclidean_distance(points[i], points[j]);
    }

    // apply Floyd-Warshall all-pairs shortest path algorithm
    for (int k = 1; k <= N; k++)
      for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
          if (matrix[i][k] + matrix[k][j] < matrix[i][j])
            matrix[i][j] = matrix[i][k] + matrix[k][j];

    double max_cuv = 1.0;
    int max_u, max_v;
    for (int u = 1; u < N; u++)
      for (int v = u + 1; v <= N; v++) {
        if (roads[u][v])
          continue;
        double cuv = 0.0, duv = euclidean_distance(points[u], points[v]);
        for (int i = 1; i <= N; i++)
          for (int j = 1; j <= N; j++) {
            double d = matrix[i][j] - min(matrix[i][u] + matrix[v][j] + duv,
              matrix[i][v] + matrix[u][j] + duv);
            if (d > epsilon)
              cuv += d;
          }
        if (cuv - 1.0 > epsilon && cuv - max_cuv > epsilon) {
          max_cuv = cuv; max_u = u; max_v = v;
        }
      }
    if (max_cuv - 1.0 > epsilon)
      cout << max_u << ' ' << max_v << endl;
    else
      cout << "No road required\n";
  }
  return 0;
}

UVa 11049 - Basic wall maze

Accepted date: 2014-10-13
Ranking (as of 2014-10-13): 483 out of 575
Language: C++

/*
  UVa 11049 - Basic wall maze

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11049_Basic_wall_maze.cpp
*/

#include <queue>
#include <utility>
#include <cstdio>
#include <cstring>
using namespace std;

const int nr_rows = 6, nr_columns = 6;
/*
enum {dir_s, dir_n, dir_e, dir_w};
const int nr_dirs = 4;
const char cdirs[nr_dirs] = {'S', 'N', 'E', 'W'};
const int dirs[nr_dirs][2] = {{1, 0}, {-1, 0}, {0, 1}, { 0, -1}};
*/
enum {dir_e, dir_w, dir_n, dir_s};
const int nr_dirs = 4;
const char cdirs[nr_dirs] = {'E', 'W', 'N', 'S'};
const int dirs[nr_dirs][2] = {{0, 1}, { 0, -1}, {-1, 0}, {1, 0}};

bool walls[nr_rows][nr_columns][nr_dirs];
bool visited[nr_rows][nr_columns];
pair<int, int> parents[nr_rows][nr_columns];

void print_path(const pair<int, int>& s)
{
  const pair<int, int>& ps = parents[s.first][s.second];
  if (ps.first != -1) {
    print_path(ps);
    int dir;
    if (ps.first < s.first)
      dir = dir_s;
    else if (ps.first > s.first)
      dir = dir_n;
    else if (ps.second < s.second)
      dir = dir_e;
    else
      dir = dir_w;
    putchar(cdirs[dir]);
  }
}

int main()
{
  while (true) {
    pair<int, int> ss, se;
    scanf("%d %d", &ss.second, &ss.first);
    if (!ss.first && !ss.second)
      break;
    ss.first--; ss.second--;
    scanf("%d %d", &se.second, &se.first);
    se.first--; se.second--;
    memset(walls, 0, sizeof(walls));
    for (int i = 0; i < 3; i++) {
      pair<int, int> ws, we;
      scanf("%d %d %d %d", &ws.second, &ws.first, &we.second, &we.first);
      if (ws.first == we.first) { // horizontal wall
        if (ws.first)
          for (int c = ws.second; c < we.second; c++)
            walls[ws.first - 1][c][dir_n] = true;
        if (ws.first < nr_rows)
          for (int c = ws.second; c < we.second; c++)
            walls[ws.first][c][dir_s] = true;
      }
      else { // vertical wall
        if (ws.second)
          for (int r = ws.first; r < we.first; r++)
            walls[r][ws.second - 1][dir_w] = true;
        if (ws.second < nr_columns)
          for (int r = ws.first; r < we.first; r++)
            walls[r][ws.second][dir_e] = true;
      }
    }

    // breadth first search
    memset(visited, 0, sizeof(visited));
    queue< pair<int, int> > sq;
    visited[ss.first][ss.second] = true;
    parents[ss.first][ss.second] = make_pair(-1, -1);
    sq.push(ss);
    while (!sq.empty()) {
      pair<int, int> s = sq.front(); sq.pop();
      if (s == se)
        break;
      for (int i = 0; i < nr_dirs; i++) {
        int r = s.first + dirs[i][0], c = s.second + dirs[i][1];
        if (r >= 0 && r < nr_rows && c >= 0 && c < nr_columns &&
          !walls[r][c][i] && !visited[r][c]) {
          visited[r][c] = true;
          parents[r][c] = s;
          sq.push(make_pair(r, c));
        }
      }
    }
    print_path(se);
    putchar('\n');
  }
  return 0;
}

UVa 10686 - SQF Problems

Accepted date: 2014-10-08
Ranking (as of 2014-10-08): 108 out of 222
Language: C++

/*
  UVa 10686 - SQF Problems

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10686_SQF_Problems.cpp

  Ugly.
*/

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <algorithm>
#include <cctype>
using namespace std;

const int C_max = 20, W_max = 10;

struct category {
  string name_;
  int nr_keywords_, nr_appear_;
  bool keywords_[W_max];

  category() {}
} categories[C_max];

bool is_duplicated_keyword(int ci, const string& w,
  multimap< string, pair<int, int> >& keywords)
{
  pair < multimap<string, pair<int, int> >::iterator, 
    multimap<string, pair<int, int> >::iterator > result = keywords.equal_range(w);
  for (multimap<string, pair<int, int> >::iterator i = result.first;
    i != result.second; ++i)
    if (i->second.first == ci)
      return true;
  return false;
}

char remove_nonalpha(char c)
{
  return (isalpha(c)) ? c : ' ';
}

int main()
{
  string line;
  istringstream iss;
  getline(cin, line);
  iss.str(line);
  int N;
  iss >> N;
  iss.clear();
  while (N--) {
    getline(cin, line);
    iss.str(line);
    int C;
    iss >> C;
    iss.clear();
    multimap< string, pair<int, int> > keywords;
      // key is a keyword, value is the index pair to categories[i].keywords_[j]
    for (int i = 0; i < C; i++) {
      category& c = categories[i];
      getline(cin, line);
      iss.str(line);
      iss >> c.name_ >> c.nr_keywords_ >> c.nr_appear_;
      iss.clear();
      for (int j = 0; j < c.nr_keywords_; ) {
        getline(cin, line);
        iss.str(line); // to remove blanks
        string w;
        iss >> w;
        iss.clear();
        if (is_duplicated_keyword(i, w, keywords))
          c.nr_keywords_--;
        else {
          keywords.insert(make_pair(w, make_pair(i, j)));
          c.keywords_[j] = false;
          j++;
        }
      }
    }
#ifdef DEBUG
    for (multimap<string, pair<int, int> >::const_iterator 
      ki = keywords.begin(), ke = keywords.end(); ki != ke; ++ki)
      cout << ki->first << " (" << ki->second.first <<
        ", " << ki->second.second << ")\n";
#endif
    while (getline(cin, line) && !line.empty()) {
      transform(line.begin(), line.end(), line.begin(), remove_nonalpha);
        // replace non-alpha chars with spaces
      iss.str(line);
      string w;
      while (iss >> w) {
        pair < multimap<string, pair<int, int> >::iterator, 
          multimap<string, pair<int, int> >::iterator > result =
            keywords.equal_range(w);
        for (multimap<string, pair<int, int> >::iterator i = result.first;
          i != result.second; ++i)
          categories[i->second.first].keywords_[i->second.second] = true;
      }
      iss.clear();
    }
    bool sqf = true;
    for (int i = 0; i < C; i++) {
      const category& c = categories[i];
      int nr_appear = 0;
      for (int j = 0; j < c.nr_keywords_; j++)
        if (c.keywords_[j])
          nr_appear++;
      if (nr_appear >= c.nr_appear_) {
        if (!sqf)
          cout << ',';
        else
          sqf = false;
        cout << c.name_;
#ifdef DEBUG
        cout << " (" << nr_appear << ")";
#endif
      }
    }
    if (sqf)
      cout << "SQF Problem.\n";
    else
      cout << endl;
  }
  return 0;
}

UVa 11507 - Bender B. Rodríguez Problem

Accepted date: 2014-10-06
Ranking (as of 2014-10-06): 160 out of 693
Language: C++

/*
  UVa 11507 - Bender B. Rodriguez Problem

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11507_Bender_B_Rodriguez_Problem.cpp
*/

#include <cstdio>

struct point {
  int x_, y_, z_;
  point() {}
  point(int x, int y, int z) : x_(x), y_(y), z_(z) {}
  point(const point& p) : x_(p.x_), y_(p.y_), z_(p.z_) {}
};

struct rotation {
  const char* s_;
  int matrix_[3][3];
} rotations[] = {
  {"+y", {{0, -1, 0}, {1, 0, 0}, {0, 0, 1}}}, // Rz(90 degree)
  {"-y", {{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}}}, // Rz(-90 degree)
  {"+z", {{0, 0, -1}, {0, 1, 0}, {1, 0, 0}}}, // Ry(-90 degree)
  {"-z", {{0, 0, 1}, {0, 1, 0}, {-1, 0, 0}}}  // Ry(90 degree)
};

point rotate_point(const point& o, const point& p, const char* s)
{
  int ri = (s[1] - 'y') * 2;
  if (s[0] == '-')
    ri++;
  const rotation& r = rotations[ri];
  point q(p.x_ - o.x_, p.y_ - o.y_, p.z_ - o.z_);
  point result;
  result.x_ =
    o.x_ + r.matrix_[0][0] * q.x_ + r.matrix_[0][1] * q.y_ + r.matrix_[0][2] * q.z_;
  result.y_ =
    o.y_ + r.matrix_[1][0] * q.x_ + r.matrix_[1][1] * q.y_ + r.matrix_[1][2] * q.z_;
  result.z_ =
    o.z_ + r.matrix_[2][0] * q.x_ + r.matrix_[2][1] * q.y_ + r.matrix_[2][2] * q.z_;
  return result;
}

int main()
{
  while (true) {
    int L;
    scanf("%d", &L);
    if (!L)
      break;
    // remember the last (left-most) point and the next to last point
    // rotate both points around j-th point
    char s[2];
    point p(L - 1, 0, 0), q(L, 0, 0);
    L--;
    while (true) {
      scanf("%s", s);
      if (s[0] != 'N') { // "No"
        q = rotate_point(p, q, s);
        break;
      }
      if (L == 1)
        break;
      L--; p.x_--;
    }
#ifdef DEBUG
    printf("(%d, %d, %d) (%d, %d, %d)\n", p.x_, p.y_, p.z_, q.x_, q.y_, q.z_);
#endif
    while (L-- > 1) {
      point o(L, 0, 0);
      scanf("%s", s);
      if (s[0] != 'N') {
        p = rotate_point(o, p, s);
        q = rotate_point(o, q, s);
#ifdef DEBUG
        printf("(%d, %d, %d) (%d, %d, %d)\n", p.x_, p.y_, p.z_, q.x_, q.y_, q.z_);
#endif
      }
    }
    if (p.x_ != q.x_)
      printf((p.x_ < q.x_) ? "+x\n": "-x\n");
    else if (p.y_ != q.y_)
      printf((p.y_ < q.y_) ? "+y\n": "-y\n");
    else
      printf((p.z_ < q.z_) ? "+z\n": "-z\n");
  }
  return 0;
}