首页 > 代码库 > Codeforces Round #243 (Div. 1)——Sereja and Squares
Codeforces Round #243 (Div. 1)——Sereja and Squares
题目链接
- 题意：
给n个点，求能组成的正方形的个数。四边均平行与坐标轴
- 大神的分析：
经典题
我们考虑每一种x坐标，显然只有<= sqrt{N}个x坐标出现了> sqrt{N}次，我们称这些为大的，其他为小的。
我们先考虑大的x和其他x之间的答案，先O(sqrt{N})枚举一个大的坐标，然后for其他的每个点，这样可以根据x坐标的差算出正方形的边长，hash检查一下就能知道这个正方形是否存在。
之后考虑小的x和小的x之间的答案，注意到我们可以对每个横坐标直接平方for，这样只有(sqrt{N})^2 + (sqrt{N})^2 + ... + (sqrt{N})^2 = N^1.5的枚举量，之后也可以hash检查。
O(N^1.5)
const int MAXN = 100001;
vector<int> vt[MAXN];
bool match(int ind, int val)
{
if (ind >= MAXN) return false;
return binary_search(all(vt[ind]), val);
}
int main()
{
// freopen("in.txt", "r", stdin);
int n, a, b, bound;
while (~RI(n))
{
REP(i, MAXN) vt[i].clear();
bound = (int)sqrt(n * 1.0);
REP(i, n)
{
RII(a, b);
vt[a].push_back(b);
}
REP(i, MAXN)
{
sort(all(vt[i]));
}
LL ans = 0;
REP(i, MAXN)
{
if (vt[i].size() > bound)
{
FF(j, i + 1, MAXN)
{
int dis = j - i;
REP(k, vt[j].size())
{
int val = vt[j][k];
if (match(j, val + dis) && match(i, val) && match(i, val + dis))
ans++;
}
}
}
else
{
REP(j, vt[i].size()) FF(k, j + 1, vt[i].size())
{
int dis = vt[i][k] - vt[i][j];
if (match(i + dis, vt[i][k]) && match(i + dis, vt[i][j]))
ans++;
}
}
}
cout << ans << endl;
}
return 0;
}
Codeforces Round #243 (Div. 1)——Sereja and Squares
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。