本文主要是介绍POJ 2002 Squares(枚举+几何),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路:先把点排序(为了减少枚举量),然后每次枚举两个点,利用公式计算出另外两个点,在set里面判断存不存在,如果存在就可以构成正方形,这样的计算,一个正方形会被计算两次,所以答案除2即可
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;typedef long long ll;
typedef pair<int, int> pii;
int n;const int N = 1005;set<pii> vis;
pii p[N];bool judge(int i, int j) {if (vis.find(make_pair(p[i].second - p[j].second + p[i].first, p[j].first - p[i].first + p[i].second)) == vis.end()) return false;if (vis.find(make_pair(p[i].second - p[j].second + p[j].first, p[j].first - p[i].first + p[j].second)) == vis.end()) return false;return true;
}int main() {while (~scanf("%d", &n) && n) {vis.clear();for (int i = 0; i < n; i++) {scanf("%d%d", &p[i].first, &p[i].second);vis.insert(make_pair(p[i].first, p[i].second));}sort(p, p + n);ll ans = 0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (judge(i, j)) ans++;}}printf("%lld\n", ans / 2);}return 0;
}
这篇关于POJ 2002 Squares(枚举+几何)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!