{"problem":{"name":"[ICPC 2021 Macao R] Laser Trap","description":{"content":"BaoBao is playing the famous game $\\textit{Elden Ring}$ these days. It's an open-world game in which you can control your character to travel from places to places. However, your character could also ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9658"},"statements":[{"statement_type":"Markdown","content":"BaoBao is playing the famous game $\\textit{Elden Ring}$ these days. It's an open-world game in which you can control your character to travel from places to places. However, your character could also enter a trap and you need to figure out how to escape. Right now, BaoBao's character is stuck in a 2-dimensional plane with deadly lasers. There are $n$ laser generators (each can be regarded as a point) shooting laser beams between every pair of them (so there are $\\frac{n(n-1)}{2}$ laser beams in total). The beams start and end at generator points and do not stretch to infinity.\n\nStarting at point $(0,0)$, BaoBao wants to escape to point $(10^{10^{10^{10^{10}}}}, 10^{10^{10^{10^{10}}}})$ without touching any laser beam or generator. In order to do so, BaoBao can ask her friend DreamGrid to remove any number of laser generators, together with any laser beam that starts or ends at these generators. Output the minimum number of laser generators that need to be erased for the escape.\n\nNote that BaoBao does not need to move in a specific direction to escape. Her escaping route can even be a curve if necessary.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($1 \\le n \\le 10^6$) indicating the number of laser generators.\n\nFor the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \\le x_i, y_i \\le 10^9$) indicating the location of the $i$-th laser generator.\n\nIt is guaranteed that no two generators coincide, and no laser beam or generator will touch $(0,0)$.\n\nIt is also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the minimum number of generators that need to be removed.\n\n[samples]\n\n## Note\n\nThe second and the third sample test cases are shown below. Solid dots and lines represent the remaining laser generators and beams, while hollow dots and dashed lines represent the removed laser generators and beams. The arrow is the escaping route.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/b0sz7cm0.png)\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/dwcsdmj6.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9658","tags":["计算几何","2021","O2优化","叉积","ICPC","双指针 two-pointer","澳门"],"sample_group":[["3\n2\n1 0\n2 0\n3\n1 0\n0 1\n-1 -1\n5\n2 -1\n1 2\n-1 2\n-2 -1\n0 -2","0\n1\n2"]],"created_at":"2026-03-03 11:09:25"}}