{"problem":{"name":"[THUSC 2019] 推恩令","description":{"content":"让我们来考虑这么一个实际的例子：有一个诸侯王，他的诸侯国里有 $n$ 个城邦，其中，城邦 $s$ 是他的诸侯国的国都。我们可以用平面直角坐标系来描述他的领土，第 $i$ 个城邦可以被看作坐标系中以 $(x_i,y_i)$ 为中心，$r_i$ 为半径的一个圆。任意两个城邦之间不会有重叠的部分（相交），也不会相互接触（相切）。 这个诸侯王有两个儿子，他想用一种简单的方式将他的国土分给他的两个儿子：在","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10343"},"statements":[{"statement_type":"Markdown","content":"让我们来考虑这么一个实际的例子：有一个诸侯王，他的诸侯国里有 $n$ 个城邦，其中，城邦 $s$ 是他的诸侯国的国都。我们可以用平面直角坐标系来描述他的领土，第 $i$ 个城邦可以被看作坐标系中以 $(x_i,y_i)$ 为中心，$r_i$ 为半径的一个圆。任意两个城邦之间不会有重叠的部分（相交），也不会相互接触（相切）。\n\n这个诸侯王有两个儿子，他想用一种简单的方式将他的国土分给他的两个儿子：在他的国土中修建一道分界渠。这道分界渠可以用坐标系中的一条直线来表示，它不能经过任意一个城邦（相交），也不能经过一个城邦的边界（相切）。这道分界渠可以将国土分为两个部分，国都 $s$ 所在的部分分给长子，另一部分分给次子。为了保证次子也可以选择一个城邦作为他的国都，分界渠两侧的国土都必须包含至少一个城邦。\n\n分界渠的修建方式可以有很多种，为了保证公平，诸侯王希望在所有本质不同的修建水渠的方式中随机地选择一种。如果两种修建分界渠的方式会把城邦分成相同的两个部分，那么这两种修建方式就被认为是本质相同的。\n\n诸侯王的次子打听到了国王的划分办法。为了提前挑选自己的国都，他想知道了解每一个城邦成为他的国都的可能性大小。他把这个任务交给了你，你需要帮助他计算：对于每一个城邦，有多少种本质不同的修建水渠的方式能使得他能选择这个城邦作为国都？\n\n## Input\n\n第一行两个整数 $n,s$，分别表示诸侯国内城邦的数量以及国都的编号。\n\n接下来 $n$ 行，每行三个整数 $x_i, y_i, r_i$，第$i$行表示第 $i$ 个城邦的中心和半径。\n\n## Output\n\n输出 $n$ 行，每行一个整数 $a_i$，第 $i$ 行的输出表示有 $a_i$ 种本质不同的修水渠方案能让次子选择第 $i$ 个城邦作为国都。\n\n[samples]\n\n## Background\n\n西汉初年，汉高祖刘邦为了更好地将土地掌握在刘家的手里，大量分封刘姓诸侯王。但随着刘邦去世，诸侯王们越来越不受中央的控制。为了削弱诸侯国的势力，汉武帝刘彻采纳朝臣主父偃的建议，实行推恩令。推恩令要求诸侯王将自己的土地分封给自己的每个子弟，而不是传位给自己的长子。这样一来，土地面积大的王国将被划分为几个土地比较小的诸侯国，诸侯王们的势力也就得到了削弱。\n\n## Note\n\n**【样例 3】**\n\n见题目附件中 `3.in/ans`。\n\n**【子任务】**\n\n对于 $100\\%$ 的数据，满足 $1\\leq s\\leq n\\leq 1000$，$0\\leq |x_i|, |y_i|, r_i \\leq 10^4$。\n\n| 子任务编号 | 分值 | 特殊限制 |\n| :--: | :--: | :--: |\n| 1 | 17 | $n\\leq 18$ |\n| 2 | 29 | $n\\leq 100$ |\n| 3 | 22 | $r_i=0$ |\n| 4 | 32 | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10343","tags":["2019","THUSC"],"sample_group":[["4 1\n0 0 0\n0 1 0\n1 0 0\n1 1 0\n","0\n3\n3\n4"],["3 1\n0 0 1\n0 3 1\n0 6 1\n","0\n1\n2"]],"created_at":"2026-03-03 11:09:25"}}