[Ynoi2002] Adaptive Hsearch&Lsearch

Luogu
IDLGP9062
Time6000ms
Memory1024MB
DifficultyP7
2002O2优化Ynoi
有 $n$ 个点 $p_1,p_2,\dots,p_n$ 在二维平面上。 有 $q$ 次询问,在第 $i$ 个询问中,给定两个数 $l_i,r_i$ ($1\leq l_i< r_i\leq n$),你需要找到一对 $(u,v)$ 满足 $l_i\leq u<v\leq r_i$,$p_u$ 和 $p_v$ 之间的欧几里得距离 $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ 最小。 ## Input 第一行两个数 $n,q$ 表示点数以及询问数。 之后 $n$ 行,第 $i$ 行包含两个整数 $x_i,y_i$ 表示 $p_i$ 的坐标。 之后 $q$ 行,第 $i$ 行包含两个整数 $l_i,r_i$ ($1\leq l_i< r_i\leq n$) 表示第 $i$ 个询问。 ## Output 对每个询问,输出一行一个整数表示最小的 $(x_u-x_v)^2+(y_u-y_v)^2$。 [samples] ## Note Idea:Claris,Solution:Claris,Code:Claris,Data:Claris&nzhtl1477 对于 $100\%$ 的数据,满足 $2 \leq n\leq 250\,000$, $1\leq q\leq 250\,000$,$1\leq x_i,y_i\leq 10^8$。
Samples
Input #1
5 5
2 4
1 1
3 3
5 1
4 2
1 5
2 3
2 4
3 5
1 3
Output #1
2
8
8
2
2
Input #2
2 1
1 1
1 1
1 2
Output #2
0
API Response (JSON)
{
  "problem": {
    "name": "[Ynoi2002] Adaptive Hsearch&Lsearch",
    "description": {
      "content": "有 $n$ 个点 $p_1,p_2,\\dots,p_n$ 在二维平面上。 有 $q$ 次询问,在第 $i$ 个询问中,给定两个数 $l_i,r_i$ ($1\\leq l_i< r_i\\leq n$),你需要找到一对 $(u,v)$ 满足 $l_i\\leq u<v\\leq r_i$,$p_u$ 和 $p_v$ 之间的欧几里得距离 $\\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ 最",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9062"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个点 $p_1,p_2,\\dots,p_n$ 在二维平面上。\n\n有 $q$ 次询问,在第 $i$ 个询问中,给定两个数 $l_i,r_i$ ($1\\leq l_i< r_i\\leq n$),你需要找到一对 $(u,v)$ 满足 $l_i\\leq u<v\\leq r_i$,$p_u$ 和 $p_v$ 之间的欧几里得距离 $\\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ 最...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments