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 =  + ;

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[];

int n;

const int MOD = ;

struct Edge {

    int val, id, tonext;

}e[maxn * ];

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 >= );

    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 *  + t1.y, one, two) &&

           tofind(t2.x *  + t2.y, one, two);

}

void work() {

//    cout << (20000 + 20000) * 20001 << endl;

    num = ;

    memset(first, , sizeof first);

    for (int i = ; i <= n; ++i) {

        scanf("%d%d", &arr[i].x, &arr[i].y);

        arr[i].x += ;

        arr[i].y += ;

        add(arr[i].x *  + arr[i].y, i);

        assert(arr[i].x *  + arr[i].y >= );

    }

//    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 = ;

    for (int i = ; i <= n; ++i) {

        for (int j = i + ; j <= n; ++j) {

            struct node t[];

            t[].x = arr[i].y - arr[j].y + arr[i].x;

            t[].y = arr[j].x - arr[i].x + arr[i].y;

            t[].x = arr[j].y - arr[i].y + arr[j].x;

            t[].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[].x < arr[i].x || t[].x == arr[i].x && t[].y < arr[i].y) {

                t[].x = arr[j].y - arr[i].y + arr[i].x;

                t[].y = arr[i].x - arr[j].x + arr[i].y;

            }

            if (t[].x < arr[j].x || t[].x == arr[j].x && t[].y < arr[j].y) {

                t[].x = arr[i].y - arr[j].y + arr[j].x;

                t[].y = arr[j].x - arr[i].x + arr[j].y;

            }

            if (check(t[], t[], i, j)) ++ans;

            t[].x = arr[i].y - arr[j].y + arr[i].x;

            t[].y = arr[j].x - arr[i].x + arr[i].y;

            t[].x = arr[j].y - arr[i].y + arr[j].x;

            t[].y = arr[i].x - arr[j].x + arr[j].y;

            if (t[].x > arr[i].x || t[].x == arr[i].x && t[].y > arr[i].y) {

                t[].x = arr[j].y - arr[i].y + arr[i].x;

                t[].y = arr[i].x - arr[j].x + arr[i].y;

            }

            if (t[].x > arr[j].x || t[].x == arr[j].x && t[].y > arr[j].y) {

                t[].x = arr[i].y - arr[j].y + arr[j].x;

                t[].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[], t[], i, j)) ans++;

        }

    }

    assert(ans >= );

    printf("%lld\n", ans / );

    return;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    while (scanf("%d", &n) != EOF && n) work();

    return ;

}

巴特西

POJ 2002 Squares 数学 + 必须hash

最新文章

热门文章