当前位置: 代码迷 >> 综合 >> 二分 poj2002 Squares
  详细解决方案

二分 poj2002 Squares

热度:98   发布时间:2023-12-14 04:09:08.0

很有意义的一道二分题

题意:给出点,问有多少个正方形


因为n<1000,就提示了可以用O(n^2)级别的代码

很容易就想到枚举正方形的两个点,那么可以通过这两个点可以得到对应的另外两个点,那么如何验证这两个点是否存在呢

当然会想到二分。先将坐标读入后排序好,然后用二分查询是否存在就可以了

因为给了3秒,所以O(n^2logn)也是可以接受的


难点:正方形并不一定是平行坐标轴的,可能是斜的,所以如何用两个已知点求得另外两个点呢?

这里有个公式可以用来变换

    double x = tx * cos(w