{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"最激动人心的太空发现发生在20世纪末。1999年,科学家们在Y1999行星上找到了一种类似蚂蚁的生物,并将其命名为M11。它只有一只眼睛长在头部的左侧,只有三脚长在身体的右侧,并且有三种行走障碍:\n\n- 由于它特殊的身体结构,它不能右转。\n- 它在行走时留下一条红色的小路。\n- 它不喜欢越过之前的红色路径,而且从来没有这样做过。\n\n\n发现号宇宙飞船传送的图片显示Y1999星球上的植物生长在行星上的特殊位置。通过对数千张图片的分析,我们发现了一个控制植物生长点的神奇坐标系统。在平面直角坐标系$xOy$中,没有两种植物有相同的$x$或$y$坐标。\nM11型虫每天需要吃掉一株植物才能存活。当它吃掉一株植物时,它就会一整天都呆在那里不动。第二天,它寻找另一株植物去那里吃它。如果它不能接触到任何其他植物,它就会在一天结束时死去。注意,它可以到达任何距离的植物。\n问题是要为M11找到一条存活时间最长的路径。\n输入是植物的$(x, y)$坐标集合。假设坐标为$(xA, yA)$的$A$是$y$坐标最小的植物。M11从点$(0,yA)$开始,朝向植物$A$。注意,路径不能交叉,所有的转弯都应该是逆时针的。还要注意,解决方案可能访问位于同一直线上的两个以上的植物。\n\n ![](https://vj.csgrandeur.cn/9d1a0a8efc770caf00f883df4ccd83aa?v\u003d1667823553)\n"}},{"title":"Input","value":{"format":"MD","content":"输入的第一行是$M(1\\leq M\\leq 10)$,要解决的数据的组数。对于每组数据,第一行是$N(1\\leq N\\leq 50)$,该组数据中的植物数量,后面是每个植物数据的$N$行。每个植物数据由三个整数组成:第一个数字是唯一的植物索引$(1..N)$,后面是两个正整数$x$和$y$,表示植物的坐标。植物按输入文件中它们的索引的递增顺序排序。假设坐标的值不超过$100$。\n"}},{"title":"Output","value":{"format":"MD","content":"对于每组数据,输出一行。第一个数是路径上的植物数量,后面是路径上访问植物的指数,按访问的顺序排列。"}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n10\n1 4 5\n2 9 8\n3 5 9\n4 1 7\n5 3 2\n6 6 3\n7 10 10\n8 8 1\n9 2 4\n10 7 6\n14\n1 6 11\n2 11 9\n3 8 7\n4 12 8\n5 9 20\n6 3 2\n7 1 6\n8 2 13\n9 15 1\n10 14 17\n11 13 19\n12 5 18\n13 7 3\n14 10 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10 8 7 3 4 9 5 6 2 1 10\n14 9 10 11 5 12 8 7 6 13 4 14 1 3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}