[Ynoi2000] hpi

Luogu

IDLGP9996

Time4000ms

Memory512MB

DifficultyP7

2000O2优化Ynoi

给定 $n$ 个互不相同的点 $(x_i,y_i)$，共 $m$ 次询问，每次询问给出 $A,B,C$，问满足 $x_i<x_j,\;y_i<y_j,\;Ax_i+By_i+C>0,\;Ax_j+By_j+C>0$ 的二元组 $(i,j)$ 的个数。 ## Input 第一行两个数 $n,m$。接下来 $n$ 行每行两个数 $x_i,y_i$，$i=1,\dots,n$。接下来 $m$ 行每行一个三个数表示一个询问 $A,B,C$。 ## Output 对每个询问，输出一行，包含一个整数，表示这个询问的答案。 [samples] ## Note Idea：nzhtl1477&ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078 对于 $100\%$ 的数据，满足 $A^2+B^2>0$，$|A|,|B|,|C|\le 10^8$，$1\le n,m\le 2\times 10^5$，$|x_i|,|y_i|\le 10^4$，$x_i,y_i$ 均匀随机选取，但保证没有重复的点。对于 $25\%$ 的数据，满足 $n,m\le 10^3$。对于另外 $25\%$ 的数据，满足 $A=0$。对于另外 $25\%$ 的数据，满足 $C=0$。对于另外 $25\%$ 的数据，无特殊限制。

Samples

Input #1

5 2
2003 -553
-141 1230
-6854 9658
9319 -1777
7773 3306
1113 -3086 -15864589
162 550 -21287

Output #1

0
1

API Response (JSON)

{
  "problem": {
    "name": "[Ynoi2000] hpi",
    "description": {
      "content": "给定 $n$ 个互不相同的点 $(x_i,y_i)$，共 $m$ 次询问，每次询问给出 $A,B,C$，问满足 $x_i<x_j,\\;y_i<y_j,\\;Ax_i+By_i+C>0,\\;Ax_j+By_j+C>0$ 的二元组 $(i,j)$ 的个数。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9996"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 个互不相同的点 $(x_i,y_i)$，共 $m$ 次询问，每次询问给出 $A,B,C$，问满足 $x_i<x_j,\\;y_i<y_j,\\;Ax_i+By_i+C>0,\\;Ax_j+By_j+C>0$ 的二元组 $(i,j)$ 的个数。\n\n## Input\n\n第一行两个数 $n,m$。\n\n接下来 $n$ 行每行两个数 $x_i,y_i$，$i=1,\\dots,n$。\n\n接下来 $m$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments