首页 > 代码库 > POJ 2002 Squares 数学 + 必须hash
POJ 2002 Squares 数学 + 必须hash
http://poj.org/problem?id=2002
只能说hash比二分快很多。随便一个hash函数都可以完爆二分。
判断是否存在正方形思路如下:
1、枚举任意两个点,作为正方形的一条边,那么,整个正方形就确定了,有两个方向。
因为,
设枚举的坐标为(x1, y1) & (x2, y2),所求的坐标是和x1,y1这个点相连,那么有方程如下。
1、垂直,向量积是0
2、边长相等,然后距离公式化简。
即可解出剩下的两个点。
然后要注意两个点要在正方形的同一侧,不然变了平行四边形了。
唤醒了我hash的回忆。
首先hash的时候,需要先把坐标平移,因为要避免出现负数的情况,所以平移40000个单位。然后再进行简单hash
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 10007 + 20; struct node { int x, y; bool operator < (const struct node & rhs) const { if (x != rhs.x) { return x < rhs.x; } else return y < rhs.y; } bool operator != (const struct node & rhs) const { return !(x == rhs.x && y == rhs.y); } } arr[2222]; int n; const int MOD = 10007; struct Edge { int val, id, tonext; }e[maxn * 2]; int first[maxn]; int num; void add(int val, int id) { ++num; int tval = val; val %= MOD; e[num].id = id; e[num].val = tval; e[num].tonext = first[val]; first[val] = num; } bool tofind(int val, int one, int two) { assert(val >= 0); int tval = val; val %= MOD; for (int i = first[val]; i; i = e[i].tonext) { if (e[i].val == tval && e[i].id != one && e[i].id != two) return true; } return false; } bool check(struct node t1, struct node t2, int one, int two) { return tofind(t1.x * 20001 + t1.y, one, two) && tofind(t2.x * 20001 + t2.y, one, two); } void work() { // cout << (20000 + 20000) * 20001 << endl; num = 0; memset(first, 0, sizeof first); for (int i = 1; i <= n; ++i) { scanf("%d%d", &arr[i].x, &arr[i].y); arr[i].x += 40020; arr[i].y += 40020; add(arr[i].x * 20001 + arr[i].y, i); assert(arr[i].x * 20001 + arr[i].y >= 0); } // cout << tofind(arr[1].x * 20001 + arr[1].y, 3, 2) << endl; // sort(arr + 1, arr + 1 + n); // for (int i = 1; i <= n; ++i) { // cout << arr[i].x << " " << arr[i].y << endl; // } // cout << endl; LL ans = 0; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { struct node t[8]; t[0].x = arr[i].y - arr[j].y + arr[i].x; t[0].y = arr[j].x - arr[i].x + arr[i].y; t[1].x = arr[j].y - arr[i].y + arr[j].x; t[1].y = arr[i].x - arr[j].x + arr[j].y; // cout << i << " " << j << endl; // cout << "*********" << endl; // for (int k = 0; k <= 1; ++k) { // cout << t[k].x << " " << t[k].y << endl; // } // cout << "**********" << endl; if (t[0].x < arr[i].x || t[0].x == arr[i].x && t[0].y < arr[i].y) { t[0].x = arr[j].y - arr[i].y + arr[i].x; t[0].y = arr[i].x - arr[j].x + arr[i].y; } if (t[1].x < arr[j].x || t[1].x == arr[j].x && t[1].y < arr[j].y) { t[1].x = arr[i].y - arr[j].y + arr[j].x; t[1].y = arr[j].x - arr[i].x + arr[j].y; } if (check(t[0], t[1], i, j)) ++ans; t[0].x = arr[i].y - arr[j].y + arr[i].x; t[0].y = arr[j].x - arr[i].x + arr[i].y; t[1].x = arr[j].y - arr[i].y + arr[j].x; t[1].y = arr[i].x - arr[j].x + arr[j].y; if (t[0].x > arr[i].x || t[0].x == arr[i].x && t[0].y > arr[i].y) { t[0].x = arr[j].y - arr[i].y + arr[i].x; t[0].y = arr[i].x - arr[j].x + arr[i].y; } if (t[1].x > arr[j].x || t[1].x == arr[j].x && t[1].y > arr[j].y) { t[1].x = arr[i].y - arr[j].y + arr[j].x; t[1].y = arr[j].x - arr[i].x + arr[j].y; } // for (int k = 0; k <= 1; ++k) { // cout << t[k].x << " " << t[k].y << endl; // } // cout << endl; if (check(t[0], t[1], i, j)) ans++; } } assert(ans >= 0); printf("%lld\n", ans / 4); return; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d", &n) != EOF && n) work(); return 0; }
POJ 2002 Squares 数学 + 必须hash
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。