很有意义的一道二分题
题意:给出点,问有多少个正方形
因为n<1000,就提示了可以用O(n^2)级别的代码
很容易就想到枚举正方形的两个点,那么可以通过这两个点可以得到对应的另外两个点,那么如何验证这两个点是否存在呢
当然会想到二分。先将坐标读入后排序好,然后用二分查询是否存在就可以了
因为给了3秒,所以O(n^2logn)也是可以接受的
难点:正方形并不一定是平行坐标轴的,可能是斜的,所以如何用两个已知点求得另外两个点呢?
这里有个公式可以用来变换
double x = tx * cos(w