Gym 102428 D Dazzling stars 题解

题目大意：给你一个二维画布，上有带权点集（即题目中说的不同亮度的星星），问是否存在一个角度，旋转整个画布，使得旋转后从下往上打印可以使得点被打印出来的顺序按点权顺序不下降。

点的个数<=1000

上手不容易有思路，得画个图。

发现点与点间相互连线可以得到一组向量。

题目对相同亮度的星星的打印顺序没有要求，所以我们只需要将亮的星星向比它严格暗的星星连线，或者反过来，然后考察这些向量。

将这些向量平移到原点后发现题目有解的情况当且仅当有一条直线能在平移的过程中在不经过任何一个向量尾的情况下抵达原点，等价于存在两条向量，它们的夹角大于等于180°。

那么我们就n^2连线，然后按极坐标排序，然后按照相邻两个向量枚举来判断夹角即可。