Mission Possible (Problem I, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 1 sec
Memory limit: 256MB
Author: Vincentius Madya Putra Indrawan

# Problem Statement

Allen, a government secret service, has been assigned to infiltrate a mafia secret base to uncover crucial information regarding the mafia’s operations.

The secret base is a rectangular bounded by $(x_L,y_L)$, $(x_L,y_R)$, $(x_R,y_L)$, and $(x_R,y_R)$ in a Cartesian coordinate system where $x_L < x_R$ and $y_L < y_R$. There are $N$ sensors placed inside the secret base. The $i^{th}$ sensor is located at $(x_i,y_i)$ and has an effective sensing radius of $r_i$ which can detect any person who is strictly within the radius of $r_i$ from $(x_i,y_i)$. In other words, the $i^{th}$ sensor can detect a person at location $(x_a,y_a)$ if and only if the Euclidean distance of $(x_i,y_i)$ and $(x_a,y_a)$ is strictly less than $r_i$. It is also known that the Euclidean distance of any two sensors $i$ and $j$ is strictly larger than $r_i + r_j$. Note that the Euclidean distance of two points, $(x_a,y_a)$ and $(x_b,y_b)$, is $\sqrt{|x_a - x_b|^2 + |y_a - y_b|^2}$.

Allen begins his infiltration mission at location $(x_s,y_s)$ and his target is located at $(x_t,y_t)$. Allen has the power to run extremely fast in a straight line while he needs to spend extra time to change his running trajectory (to adjust his footing). Although he is a fast runner, he still needs to make sure that none of the sensors detect him while he is running, i.e. there is no point in his running trajectory which is strictly within a sensor effective sensing radius.

Let $P = \{(x_{p_1}, y_{p_1}), \ldots, (x_{p_{|P|}}, y_{p_{|P|}})\}$ be the set of locations where Allen changes his running trajectory, thus, Allen’s running trajectory with $P$ is $(x_s,y_s) \rightarrow (x_{p_1}, y_{p_1}) \rightarrow \ldots \rightarrow (x_{p_{|P|}}, y_{p_{|P|}}) \rightarrow (x_t,y_t)$ where $(x_a,y_a) \rightarrow (x_b,y_b)$ implies that Allen is running from $(x_a,y_a)$ to $(x_b,y_b)$ in a straight line. The set $P$ is feasible if and only if with $P$, Allen is not detected by any sensor and is not running out of the secret base (although, Allen is allowed to run along the secret base perimeter). Note that $x_p$ and $y_p$, $(x_p, y_p) \in P$, are not necessarily integers; they can be real numbers.

Your task in this problem is to find any one feasible $P$ which contains no more than 1000 points.

# Input

Input begins with a line containing five integers: $N$ $x_L$ $y_L$ $x_R$ $y_R$ $(0 \leq N \leq 50; 0 \leq x_L < x_R \leq 1000; 0 \leq y_L < y_R \leq 1000)$ representing the number of sensors and the secret base $(x_L, y_L, x_R, y_R)$, respectively.  
The next line contains two integers: $x_s$ $y_s$ $(x_L < x_s < x_R; y_L < y_s < y_R)$ representing Allen’s initial location.  
The next line contains two integers: $x_t$ $y_t$ $(x_L < x_t < x_R; y_L < y_t < y_R)$ representing Allen’s target location. It is guaranteed that $x_s \neq x_t$ or $y_s \neq y_t$.  
The next $N$ lines each contains three integers: $x_i$ $y_i$ $r_i$ $(x_L < x_i - r_i < x_i + r_i < x_R; y_L < y_i - r_i < y_i + r_i < y_R; 1 \leq r_i \leq 1000)$ representing a sensor at location $(x_i,y_i)$ with an effective sensing radius of $r_i$. It is guaranteed that the Euclidean distance of any two sensors $i$ and $j$ is larger than $r_i + r_j$. It is also guaranteed that the Euclidean distance of $(x_s,y_s)$ and $(x_t,y_t)$ to any sensor $i$ is larger than $r_i$.

# Output

Output in a line an integer representing the size of a feasible $P$. The next $|P|$ lines each contains two real numbers (separated by a single space); the $j^{th}$ line contains $x_j$ $y_j$ representing the $j^{th}$ point in $P$. You may output any feasible $P$ with no more than 1000 points.

Due to the nature of the output (floating point), let us define an epsilon $\epsilon$ to be $10^{-6}$ to verify the output.  
Consider $Q_1 = (x_s, y_s)$, $Q_{j+1} = P_j$ for all $1 \leq j \leq |P|$, and $Q_{|P|+2} = (x_t, y_t)$.  
Then, $P$ is considered correct if and only if $P$ contains no more than 1000 points and all of the following are satisfied:

- $x_L - \epsilon \leq x_{p_k} \leq x_R + \epsilon$ and $y_L - \epsilon \leq y_{p_k} \leq y_R + \epsilon$ for all $1 \leq k \leq |P|$ (Allen is not running out of the secret base).

- For all $1 \leq k < |Q|$, let $S_k$ be the line segment connecting $Q_k$ and $Q_{k+1}$ (Allen is running in straight line).  
  For all $1 \leq i \leq N$, let $(x_{k,i}, y_{k,i})$ be the point along $S_k$ that is the closest to the $i^{th}$ sensor’s location, $(x_i, y_i)$.  
  Let $d_{k,i}$ be the Euclidean distance between $(x_{k,i}, y_{k,i})$ and $(x_i, y_i)$.  
  Then, the constraint $r_i \leq d_{k,i} + \epsilon$ should be satisfied (Allen is not detected by any sensor).

- All points in $Q$ are distinct.  
  Two points, $(x_a, y_a)$ and $(x_b, y_b)$, are considered distinct if and only if $|x_a - x_b| > \epsilon$ or $|y_a - y_b| > \epsilon$.

# Sample Input #1
```
3 2 2 50 26
4 14
48 14
15 13 7
36 16 6
46 18 3
```
# Sample Input #2
```
1 0 0 1000 1000
100 501
900 501
500 251 250
```
# Sample Output #1
```
2
13.25 23.1234567
36.591003 7.1
```
# Sample Output #2
```
0
```
Explanation for the sample input/output #1

![IMAGE](icpc-jakarta-2019-mission-1.png)


The figure above shows the P from the sample output. Note that there exists a feasible P with only one point in this sample, although you are not required to find such P.

Sample inputs:
3 2 2 50 26
4 14
48 14
15 13 7
36 16 6
46 18 3

1 0 0 1000 1000
100 501
900 501
500 251 250

Sample outputs:
2
13.25 23.1234567
36.591003 7.1

0

# Solution Analysis
Analysis author: Wiwit Rifai'

We need a basic understanding of graph theory (pathfinding) and geometry (tangent and line) to solve this problem. The big idea is: The feasible path can be found through some tangent/boundary line segments.

First, let us deal with the geometry aspect of this problem. Find the tangent lines between Allen’s initial/target points to any circles, and the tangent lines between any two circles. Next, make each tangent line into a tangent line segment such that:

1. The two objects (points or circles) which create the tangent line are still connected by the line segment,  
2. The line segment spans as much as possible without crossing any circle or going out of the boundaries.

If the tangent line segment cannot connect the two objects which create it (e.g., it crosses another circle), then we can drop that tangent line. Next, find all the boundary line segments; there are 4 boundaries (the rectangle’s sides), but we need to break them down into some line segments if there is a circle crossing the boundaries.

![IMAGE](icpc-jakarta-2019-mission-2.png)

Now, let us transform this problem into a graph problem. Let the line segments be the vertices, and an edge implies that the two line segments have an intersection point. The starting vertex is all line segments that go through Allen’s initial point, while the goal vertex is all line segments that go through Allen’s target point. Finally, simply do a *breadth-first search* (BFS) to find the path from the starting vertex to the goal vertex. You need to keep the parent node as you do BFS to print the points.


Special judge (C++ scorer):
#include <bits/stdc++.h>
using namespace std;

int ac() {
  puts("AC");
  return 0;
}

int wa(string message) {
  fprintf(stderr, "%s\n", message.c_str());
  puts("WA");
  return 0;
}

typedef long long Integer;
typedef long double Number;

Number sqr(const Number &num) {
  return num * num;
}

struct Point {
  Number x;
  Number y;

  Point() {}

  Point(Number _x, Number _y) {
    x = _x;
    y = _y;
  }

  Point(const Point &other) {
    x = other.x;
    y = other.y;
  }

  bool operator==(const Point &other) const {
    return make_pair(x, y) == make_pair(other.x, other.y);
  }

  bool operator<(const Point &other) const {
    return make_pair(x, y) < make_pair(other.x, other.y);
  }
};

struct Line {
  Point st;
  Point nd;

  Line() {}

  Line(Point _st, Point _nd) {
    st = _st;
    nd = _nd;
  }

  Line(const Line &other) {
    st = other.st;
    nd = other.nd;
  }

  Number dx() const {
    return nd.x - st.x;
  }

  Number dy() const {
    return nd.y - st.y;
  }

  Number d() const {
    return sqrt(sqr(dx()) + sqr(dy()));
  }
};

struct Circle {
  Point o;
  Number r;

  Circle() {}

  Circle(Point _o, Number _r) {
    o = _o;
    r = _r;
  }

  Circle(const Circle &other) {
    o = other.o;
    r = other.r;
  }
};

Number distance(const Point &p1, const Point &p2) {
  return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}

const Number OUT_OF_BOUND_EPS = 1e-6;
const Number CONSECUTIVE_POINTS_EPS = 1e-6;
const Number INTERSECTING_CIRCLE_EPS = 1e-6;

int main(int argc, char *argv[])
{
  FILE *in = fopen(argv[1], "r");
  FILE *out = fopen(argv[2], "r");  // Judge's
  FILE *con = fopen(argv[3], "r");

  int N;
  Integer xl, yl, xr, yr, xs, ys, xt, yt;
  fscanf(in, "%d %lld %lld %lld %lld", &N, &xl, &yl, &xr, &yr);
  fscanf(in, "%lld %lld", &xs, &ys);
  fscanf(in, "%lld %lld", &xt, &yt);

  Point L = Point(Number(xl), Number(yl));
  Point R = Point(Number(xr), Number(yr));
  Point S = Point(Number(xs), Number(ys));
  Point T = Point(Number(xt), Number(yt));

  vector<Circle> circles;
  for (int i = 0; i < N; ++i) {
    Integer x, y, r;
    fscanf(in, "%lld %lld %lld", &x, &y, &r);
    circles.push_back(Circle(Point(x, y), r));
  }

  int K;
  if (fscanf(con, "%d", &K) != 1) {
    return wa("Unexpected EOF.");
  }

  if (K < 0 || K > 1000) {
    return wa("K is out of the allowed bound."); 
  }

  vector<Point> P = {S};  
  for (int i = 0; i < K; ++i) {
    Number x, y;
    if (fscanf(con, "%Lf %Lf", &x, &y) != 2) {
      return wa("Unexpected EOF.");
    }

    if (x + OUT_OF_BOUND_EPS < L.x || x - OUT_OF_BOUND_EPS > R.x) {
      return wa("Point out of bound.");
    }
    if (y + OUT_OF_BOUND_EPS < L.y || y - OUT_OF_BOUND_EPS > R.y) {
      return wa("Point out of bound.");
    }
    P.push_back(Point(x, y));
  }
  P.push_back(T);

  for (int i = 0; i < P.size(); ++i) {
    for (int j = i + 1; j < P.size(); ++j) {
      if (fabs(P[i].x - P[j].x) <= CONSECUTIVE_POINTS_EPS &&
          fabs(P[i].y - P[j].y) <= CONSECUTIVE_POINTS_EPS) {
        return wa("Two points considered the same.");
      }
    }
  }

  for (int i = 0; i < P.size() - 1; ++i) {
    const Line l = Line(P[i], P[i + 1]);

    const Number a = l.dy();
    const Number b = -l.dx();
    const Number c = P[i].y * l.dx() - P[i].x * l.dy();

    for (const Circle &circle : circles) {
      // Point on the line closest to circle origin
      const Number x =
          (b * (b * circle.o.x - a * circle.o.y) - a * c) / (sqr(a) + sqr(b));
      const Number y =
          (a * (-b * circle.o.x + a * circle.o.y) - b * c) / (sqr(a) + sqr(b));
      const Point p = Point(x, y);

      Number minimum_distance;
      if (min(l.st.x, l.nd.x) <= x + 1E-9 && x <= max(l.st.x, l.nd.x) + 1E-9 &&
          min(l.st.y, l.nd.y) <= y + 1E-9 && y <= max(l.st.y, l.nd.y) + 1E-9) {
        minimum_distance = distance(p, circle.o);
      } else {
        minimum_distance = min(
            distance(P[i], circle.o), distance(P[i + 1], circle.o));
      }

      if (minimum_distance < circle.r - INTERSECTING_CIRCLE_EPS) {
        return wa("Path intersects a circle.");
      }
    }
  }

  fscanf(con, "\n");
  char dummy;
  if (fscanf(con, "%c", &dummy) == 1) {
    return wa("Expected EOF.");
  }

  return ac();
}