H. Compass

Codeforces

IDCF10159H

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

The university of Algoland is located in a single huge building. It is great. It is the best building in the world. It only uses the best angles: the right angle! But the building is so huge that it is also very confusing to new students, because it is very easy to get lost. The rector of Algoland's university, a former professor in physics, had a great idea to prevent students from getting lost in the future: He bought an incredibly strong magnet with the intention of placing it somewhere inside the building and using it as an emergency meeting point. On the first day of the semester, every student gets a free compass. With that compass the student can always tell the direction towards the magnet (the magnet is so strong that it completely dominates the earth's magnetic field). If a student gets lost, she can follow the following simple procedure to get to the emergency meeting point at the magnet's location: In the corner case where you want to walk parallel to a wall at the exact coordinate of a wall, you are not stopped by the wall. We assume here that you are infinitesimally small (which is true in proportion to the size of the building). The rector now wants your help to place the magnet inside the building in such a way that every student can reach it (following the procedure above) no matter where inside the building the student gets lost. Actually, you just have to decide if this is possible or not. The first line contains an integer N, the number of points, 4 ≤ N ≤ 103. Each of the following N lines contains two coordinates x and y (0 ≤ x ≤ 103 and 0 ≤ y ≤ 103). Each line describes a corner point of the single wall that delimits the inside from the outside of the building. The points are given in clockwise order and all the angles are guaranteed to be 90 degrees. Print a single line containing a single word: either _SAFETY_ if it is possible to place the magnet such that one is always able to find it, or _DANGER_ otherwise. ## Input The first line contains an integer N, the number of points, 4 ≤ N ≤ 103.Each of the following N lines contains two coordinates x and y (0 ≤ x ≤ 103 and 0 ≤ y ≤ 103). Each line describes a corner point of the single wall that delimits the inside from the outside of the building. The points are given in clockwise order and all the angles are guaranteed to be 90 degrees. ## Output Print a single line containing a single word: either _SAFETY_ if it is possible to place the magnet such that one is always able to find it, or _DANGER_ otherwise. [samples]

**Definitions** Let $ P = (p_1, p_2, \dots, p_N) $ be a sequence of $ N $ points in $ \mathbb{R}^2 $, given in clockwise order, representing the corners of a rectilinear polygon (all internal angles are $ 90^\circ $). **Constraints** 1. $ 4 \leq N \leq 10^3 $ 2. $ 0 \leq x_i, y_i \leq 10^3 $ for all $ i \in \{1, \dots, N\} $ 3. The polygon is simple (non-self-intersecting) and axis-aligned (edges are horizontal or vertical). **Objective** Determine whether there exists a point $ m \in \text{int}(P) $ (interior of the polygon) such that, for every point $ s \in \text{int}(P) $, the axis-aligned path from $ s $ to $ m $ (moving only north, south, east, or west, without crossing the boundary) exists. This is equivalent to checking whether the polygon is **rectilinearly convex** (i.e., the intersection of the polygon with any horizontal or vertical line is connected). **Output** - Print **SAFETY** if such a point $ m $ exists. - Print **DANGER** otherwise.

API Response (JSON)

{
  "problem": {
    "name": "H. Compass",
    "description": {
      "content": "The university of Algoland is located in a single huge building. It is great. It is the best building in the world. It only uses the best angles: the right angle! But the building is so huge that it i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10159H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The university of Algoland is located in a single huge building. It is great. It is the best building in the world. It only uses the best angles: the right angle! But the building is so huge that it i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P = (p_1, p_2, \\dots, p_N) $ be a sequence of $ N $ points in $ \\mathbb{R}^2 $, given in clockwise order, representing the corners of a rectilinear polygon (all internal angles...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments