BZOJ2338 数矩形
本来以为是上回那道数正方形的原题的。结果发现不要求边与座标轴平行,于是我就naive了。然后数据结构变身计算几何一堆东西吼吼。 矩形的对角线相等且互相平分(来自初二数学书)。把所有点对的中点找出来,把所有相等且平分的放一起用单调性,有点像旋转卡(qia3)壳(qiao4)的做法。jason_yu说暴力枚举都能过,而且他跑得比我快! 计算几何也写得比较naive。调了半天啊。 毕竟我弱嘛。 #include <cstdio> #include <cmath> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) const double eps = 1e-8; const int maxn = 1509; #define sqr(x) ((x)*(x)) #define dist(a,b) (sqr(a.x-b.x)+sqr(a.y-b.y)) #define nextele(_x_) ((_x_+1==r)?(l):(_x_+1)) struct point { qw x, y; point(qw x0 = 0, qw y0 = 0) { x = x0, y = y0; } inline point operator =(const point& a) {...