首页 > 代码库 > 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个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。