#K68232. Circle Placement Feasibility

    ID: 32819 Type: Default 1000ms 256MiB

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.

## sample
10 10
2
2 2 2
8 8 2
Feasible