{"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}$ 最小。\n\n## Input\n\n第一行两个数 $n,q$ 表示点数以及询问数。\n\n之后 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$ 表示 $p_i$ 的坐标。\n\n之后 $q$ 行，第 $i$ 行包含两个整数 $l_i,r_i$ ($1\\leq l_i< r_i\\leq n$) 表示第 $i$ 个询问。\n\n## Output\n\n对每个询问，输出一行一个整数表示最小的 $(x_u-x_v)^2+(y_u-y_v)^2$。\n\n[samples]\n\n## Note\n\nIdea：Claris，Solution：Claris，Code：Claris，Data：Claris&nzhtl1477\n\n对于 $100\\%$ 的数据，满足 $2 \\leq n\\leq 250\\,000$, $1\\leq q\\leq 250\\,000$，$1\\leq x_i,y_i\\leq 10^8$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9062","tags":["2002","O2优化","Ynoi"],"sample_group":[["5 5\n2 4\n1 1\n3 3\n5 1\n4 2\n1 5\n2 3\n2 4\n3 5\n1 3","2\n8\n8\n2\n2"],["2 1\n1 1\n1 1\n1 2","0"]],"created_at":"2026-03-03 11:09:25"}}