UVa 10553 - Treasure Map

Accepted date: 2011-06-19
Ranking (as of 2013-08-14): 13 out of 203
Language: C++

/*
  UVa 10553 - Treasure Map

  To build using Visucal Studio 2008:
    cl -EHsc -O2 treasure_map.cpp
*/

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cfloat>
#include <cmath>
using namespace std;

#define EPSILON FLT_EPSILON /* DBL_EPSILON */

const double pi = 2.0 * acos(0.0); // 3.14159265358979323846

struct point {
  double x, y;

  point() : x(0.0), y(0.0) {}
  point(double _x, double _y) : x(_x), y(_y) {}
  point(const point &p) : x(p.x), y(p.y) {}
  bool operator==(const point& p) const
    {return fabs(x - p.x) <= EPSILON && fabs(y - p.y) <= EPSILON;}
};

struct line {
  double a; // x-coefficient
  double b; // y-coefficient
  double c; // constant term
};

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

void points_to_line(const point& p1, const point& p2, line& l)
{
  if (p1.x == p2.x) {
    l.a = 1; l.b = 0; l.c = -p1.x;
  }
  else {
    l.b = 1;
    l.a = -(p1.y - p2.y) / (p1.x - p2.x);
    l.c = -(l.a * p1.x) - l.b * p1.y;
  }
}

void point_and_slope_to_line(const point& p, double m, line& l)
{
  l.a = -m;
  l.b = 1;
  l.c = -(l.a * p.x + l.b * p.y);
}

inline bool parallelQ(const line& l1, const line& l2)
{
  return fabs(l1.a - l2.a) <= EPSILON && fabs(l1.b - l2.b) <= EPSILON;
}

inline bool same_lineQ(const line& l1, const line& l2)
{
  return parallelQ(l1, l2) && fabs(l1.c - l2.c) <= EPSILON;
}

bool intersection_point(const line& l1, const line& l2, point& p)
{
  if (same_lineQ(l1, l2)) {
#ifdef DEBUG
    printf("Warning: Identical lines, all points intersect.\n");
#endif
    return false;
  }
  if (parallelQ(l1, l2)) {
#ifdef DEBUG
    printf("Error: Distinct parallel lines do not intersect.\n");
#endif
    return false;
  }
  p.x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
  if (fabs(l1.b) > EPSILON) // test for vertical line
    p.y = - (l1.a * p.x + l1.c) / l1.b;
  else
    p.y = - (l2.a * p.x + l2.c) / l2.b;
  return true;
}

bool in_range(double d, double a, double b)
{
  return d >= min(a, b) - EPSILON && d <= max(a, b) + EPSILON;
}

bool point_in_box(const point& p, const point& b1, const point& b2)
{
  return in_range(p.x, b1.x, b2.x) && in_range(p.y, b1.y, b2.y);
}

bool closest_point_from_line_segment(const point& p, const point& sp1,
  const point& sp2, point& closest_p)
{
  // get a line segment that connects sp1 and sp2
  line l;
  points_to_line(sp1, sp2, l);
  if (fabs(l.b) <= EPSILON) {  // vertical line
    if (in_range(p.y, sp1.y, sp2.y)) {
      closest_p.x = -l.c; closest_p.y = p.y;
      return true;
    }
    else
      return false;
  }
  if (fabs(l.a) <= EPSILON) {  // horizontal line
    if (in_range(p.x, sp1.x, sp2.x)) {
      closest_p.x = p.x; closest_p.y = -l.c;
      return true;
    }
    else
      return false;
  }
  line perp; // perpendicular to l through p
  point_and_slope_to_line(p, 1.0 / l.a, perp); // non-degenerate line
  intersection_point(l, perp, closest_p);
  return point_in_box(closest_p, sp1, sp2);
}

void generate_compass_points(map<string, double>& compass_points)
{
  const pair<string, double> cps[] = {
    make_pair("N", 0.5 * pi), make_pair("NbE", 0.4375 * pi),
    make_pair("NNE", 0.375 * pi), make_pair("NEbN", 0.3125 * pi),
    make_pair("NE", 0.25 * pi), make_pair("NEbE", 0.1875 * pi),
    make_pair("ENE", 0.125 * pi), make_pair("EbN", 0.0625 * pi),
    make_pair("E", 0.0), make_pair("EbS", -0.0625 * pi),
    make_pair("ESE", -0.125 * pi), make_pair("SEbE", -0.1875 * pi),
    make_pair("SE", -0.25 * pi), make_pair("SEbS", -0.3125 * pi),
    make_pair("SSE", -0.375 * pi), make_pair("SbE", -0.4375 * pi),
    make_pair("S", -0.5 * pi), make_pair("SbW", -0.5625 * pi),
    make_pair("SSW", -0.625 * pi), make_pair("SWbS", -0.6875 * pi),
    make_pair("SW", -0.75 * pi), make_pair("SWbW", -0.8125 * pi),
    make_pair("WSW", -0.875 * pi), make_pair("WbS", -0.9375 * pi),
    make_pair("W", pi), make_pair("WbN", 0.9375 * pi),
    make_pair("WNW", 0.875 * pi), make_pair("NWbW", 0.8125 * pi),
    make_pair("NW", 0.75 * pi), make_pair("NWbN", 0.6875 * pi),
    make_pair("NNW", 0.625 * pi), make_pair("NbW", 0.5625 * pi)
  };
  for (size_t i = 0, n = sizeof(cps) / sizeof(pair<string, double>); i < n; i++)
    compass_points.insert(cps[i]);
}

void convert_to_point(double angle, int distance, point& p)
{
  p.x += cos(angle) * distance;
  p.y += sin(angle) * distance;
}

void convert_to_point(double angle, int distance, const point& previous,
  point& current)
{
  current.x = previous.x + cos(angle) * distance;
  current.y = previous.y + sin(angle) * distance;
}

int main(int /* argc */, char** /* argv */)
{
  map<string, double> compass_points;
  generate_compass_points(compass_points);
  while (true) {
    int nr_steps; // number of steps
    cin >> nr_steps;
    if (!nr_steps)
      break;
    vector<double> angles(nr_steps + 1);
    vector<int> paces(nr_steps + 1);
    angles[0] = 0.0; paces[0] = 0;
    point x; // point marked X where the treasure is located
    for (int i = 0; i < nr_steps; i++) {
      string cp; // compass point
      cin >> cp >> paces[i + 1];
      // get an angle (between -pi and pi) for the compass_point, and then
      // get the point coordinates from the angle, and the paces
      convert_to_point(angles[i + 1] = compass_points[cp], paces[i + 1], x);
    }
    double degree; // degree from north
    cin >> degree;
    double angle = degree * pi / 180.0; // convert to the angle in radian
    vector<point> points(nr_steps + 1);
    points[0].x = points[0].y = 0.0; // the first point is the original point
    for (int i = 0; i < nr_steps; i++) // rotate points by the angle
      convert_to_point(angles[i + 1] + angle, paces[i + 1], points[i],
        points[i + 1]);
    double least_distance = euclidean_distance(points[0], x);
    for (int i = 0; i < nr_steps; i++) {
      // get the closest point on the line segment from x
      point closest_p;
      double distance = (closest_point_from_line_segment(x,
          points[i], points[i + 1], closest_p)) ?
        euclidean_distance(closest_p, x) :
        min(euclidean_distance(points[i], x),
          euclidean_distance(points[i + 1], x));
      least_distance = min(least_distance, distance);
    }
    printf("%.2f\n", least_distance);
  }
  return 0;
}