F. At the Hell's Threshold

Codeforces
IDCF10046F
Time2000ms
Memory256MB
Difficulty
English · Original
Formal · Original
Desmond and Thorwald rush to rescue! They are making their way through the secret underground tunnel, magically connecting the human world with Enia. But the tunnel forks into n passages, each having an ancient elven rune carefully painted above. As you might guess, not all the passages lead to Enia: some of them lead to other worlds, most of which are not suitable for life. Ancient elven runes are the sets of luminous points, in a certain way arranged relative to each other. Each of the runes denotes the name of the world where the corresponding passage leads, in the ancient elven language. Fortunately, one tavern master had sketched the image of the desired rune on a napkin and gave it to the heroes. The image is made not in full size but is oriented correctly, i.e. from the coordinates of points on the image it is possible to get the coordinates of points on the rune by zoom (equal by all directions) and translation. The first line contains two integers separated by the space: n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10000) — the number of passages marked by runes and the number of points each rune made of. The next lines contains 2m integers each, separated by the spaces: xij and yij ( - 109 ≤ xij, yij ≤  + 109) — the coordinates of the j-th point on the i-th image of the rune. The first image corresponds to tavern master's drawing, and the other n correspond to the runes above passages. For each image, all points on it are different. Output n lines. In the i-th line output «_YES_» (without quotes) if the i-th passage leads to Enia, otherwise output «_NO_» (without quotes) in this line. ## Input The first line contains two integers separated by the space: n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 10000) — the number of passages marked by runes and the number of points each rune made of.The next lines contains 2m integers each, separated by the spaces: xij and yij ( - 109 ≤ xij, yij ≤  + 109) — the coordinates of the j-th point on the i-th image of the rune. The first image corresponds to tavern master's drawing, and the other n correspond to the runes above passages. For each image, all points on it are different. ## Output Output n lines. In the i-th line output «_YES_» (without quotes) if the i-th passage leads to Enia, otherwise output «_NO_» (without quotes) in this line. [samples]
**Definitions** Let $ n \in \mathbb{Z} $ be the number of passages, $ m \in \mathbb{Z} $ be the number of points per rune. Let $ P = (p_1, p_2, \dots, p_m) $, where $ p_j = (x_j, y_j) \in \mathbb{R}^2 $, be the reference rune (first image). Let $ Q_i = (q_{i1}, q_{i2}, \dots, q_{im}) $, where $ q_{ij} = (x_{ij}, y_{ij}) \in \mathbb{R}^2 $, be the $ i $-th candidate rune ($ i \in \{1, \dots, n\} $). **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 1 \leq m \leq 10000 $ 3. All points in each $ P $ and $ Q_i $ are distinct. 4. $ -10^9 \leq x_{ij}, y_{ij} \leq 10^9 $ **Objective** For each $ i \in \{1, \dots, n\} $, determine whether $ Q_i $ is geometrically similar to $ P $ under a uniform scaling and translation (i.e., there exists $ s > 0 $ and $ \vec{t} \in \mathbb{R}^2 $ such that $ q_{ij} = s \cdot p_j + \vec{t} $ for all $ j \in \{1, \dots, m\} $, up to point reordering). Output "YES" if similar, "NO" otherwise.
API Response (JSON)
{
  "problem": {
    "name": "F. At the Hell's Threshold",
    "description": {
      "content": "Desmond and Thorwald rush to rescue! They are making their way through the secret underground tunnel, magically connecting the human world with Enia. But the tunnel forks into n passages, each having ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10046F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Desmond and Thorwald rush to rescue! They are making their way through the secret underground tunnel, magically connecting the human world with Enia. But the tunnel forks into n passages, each having ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of passages, $ m \\in \\mathbb{Z} $ be the number of points per rune.  \nLet $ P = (p_1, p_2, \\dots, p_m) $, where $ p_j = (x_j, y_j) \\in \\mathbb{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments