来自 2026 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2026)决赛。
题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。
随着流光解密挑战的圆满完成,全息光树被完全点亮,盛大的十周年庆典也悄然步入尾声。作为庆典的最后环节,小 T 和小 S 邀请大家来到了一块描绘着漫天星图的数字画板前。
岁月流转,过往绘就的星座连线已随着时间悄然淡化,此时的画板又回到了仅有孤立星辰散布的模样。小 S 递给现场的大家特制的星图笔,希望大家能重新补全这份星图。为了使重绘的纪念星图呈现出极致的美感,连结星辰时必须保持结构的平衡。
伴随着悠扬的旋律,大家纷纷上前,希望能在这片星海中点亮尽可能多的星座,为这场十周年纪念晚会留下最璀璨的收官之作。
画板上共有 颗星辰,可将其视为二维平面上的点。第 颗星辰的坐标为 。已知所有星辰的横坐标两两不同,纵坐标也两两不同。
每次绘制星座时,你需要从这 颗星辰中选取三颗,将它们两两连接构成一个三角形。为了体现平衡的美感,该三角形必须满足特定的边界要求:存在一个四条边均平行于坐标轴的矩形,使得该三角形的三个顶点恰好都落在这个矩形的边界上。同时,为了维持星图的清晰结构,所有连结出的三角形的内部区域(不包含顶点与边界)必须两两互不相交。
请你计算出最多能成功绘制多少个星座,并给出一组具体的绘制方案。