#K68232. Circle Placement Feasibility
Circle Placement Feasibility
Circle Placement Feasibility
You are given a rectangular canvas of width \(W\) and height \(H\). There are \(n\) circles provided. Each circle is described by its center coordinates \((x, y)\) and its radius \(r\). Your task is to determine if all the circles can be placed within the canvas such that:
- Every circle is completely inside the boundaries of the canvas. In other words, for every circle, the following must hold:
\[ x - r \ge 0, \quad x + r \le W, \quad y - r \ge 0, \quad y + r \le H \]
- No two circles overlap. That is, for any two distinct circles with centers \((x_i, y_i)\) and \((x_j, y_j)\) and radii \(r_i\) and \(r_j\), the Euclidean distance between their centers should be at least \(r_i + r_j\):
\[ \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \ge r_i+r_j \]
Output Feasible if all circles meet these conditions, otherwise output Not Feasible.
inputFormat
The input is read from standard input and has the following format:
W H n x1 y1 r1 x2 y2 r2 ... xn yn rn
Where:
- \(W\) and \(H\) (integers) specify the canvas dimensions.
- \(n\) is the number of circles.
- Each of the next \(n\) lines contains three integers \(x\), \(y\), and \(r\) representing a circle's center and its radius.
outputFormat
Output a single line to standard output: either Feasible if the arrangement of circles is valid, or Not Feasible otherwise.
## sample10 10
2
2 2 2
8 8 2
Feasible