poj2002 Squares

IAmL posted @ 2009年4月02日 06:11 in 解题报告 with tags poj2002 Squares解题报告 , 6607 阅读

经过无数WA，TLE和一个诡异的CE之后，我终于把poj2002的时间由3300+MS刷到了735MS，虽然离最牛B的100+MS还有一段距离，不过能达到这个时间，我还是很高兴。这题其实思路不难，就是枚举两个点，然后把这两个点的连线作为正方形的一边，然后找能与这两个点构成正方形的另外两个点是否存在在给出的点集里面。在一个集合里面找点的方法有很多，比如二分搜索和hash都可以。当然，用hash肯定会快很多（前提是能很好的解决冲突问题）。

我提交的所有WA和一半的TLE，都是归功于基础不扎实，导致连个二分搜索都写不好……。PS：另一半TLE归功于hash写不好……

虽说hash和二分搜索写不好是一个原因，另一个原因就是求正方形另外两个点的方法。一开始，我用了最粗暴的方法：求斜率，之后用距离求另外的点，然后就不断提交，不断WA，很郁闷。然后看了一下别人的做法。发现他们求正方形的另外两个点的方法很巧妙（虽然一开始我看不出是怎么求出来的，不过之后经过啊通的一句之后就豁然开朗了）

下面说一下简单的证明：

已知两个点，然后做出两个全等三角形。之后就得出结论(x1+|y1-y2|, y1+|x1-x2|),(x2+|y1-y2|,y2+|x1-x2|)。当然这只是一种情况，其他情况类似。

后记：

1.本题提高效率的方法：

a.用hash而不用二分搜索；

b.制定一个好的寻找正方形点的策略，从而减少搜索次数；

＝＝＝＝＝＝＝＝＝＝＝＝＝＝继续华丽的分割线＝＝＝＝＝＝＝＝＝＝＝＝

＝＝＝＝＝二分搜索的代码＝＝＝＝＝＝

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define N 1001

int n;

struct point
{
int x, y;
}p[N];

bool cmp(point a, point b)
{
if ((a.x < b.x) || (a.x == b.x && a.y < b.y)) return true;

return false;
}

bool BS(int& x, int& y)
{
int m, l = 0, r = n - 1;
bool found = false;

while (l <= r)
{
m = (l + r) / 2;

if (p[m].x == x)
{
found = true;
break;
}
else
{
if (p[m].x >= x) r = m - 1;
else l = m + 1;
}
}

if (!found) return false;
if (p[m].y == y) return true;

l = r = m;
while (p[l].x == x) l--;
while (p[r].x == x) r++;

if (l < n - 1) l++;
if (r > 0) r--;
while (l <= r)
{
m = (l + r) / 2;

if (p[m].y == y) return true;

if (p[m].y >= y) r = m - 1;
else l = m + 1;
}

return false;
}

int main()
{
int i, j, sum, bound;
int a1, a2, b1, b2, ab1, ab2, x1, y1, x2, y2, x3, y3, x4, y4;

while (cin >> n, n)
{
for (i = 0; i < n; i++) cin >> p[i].x >> p[i].y;

sort(p, p + n, cmp);

bound = n - 3;
for (sum = 0, i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
a1 = p[i].x;
a2 = p[i].y;
b1 = p[j].x;
b2 = p[j].y;
ab1 = a1 - b1;
ab2 = a2 - b2;
x1 = a1 + ab2;
y1 = a2 - ab1;
x2 = b1 + ab2;
y2 = b2 - ab1;

if (BS(x1, y1) && BS(x2, y2)) sum++;

x3 = a1 - ab2;
y3 = a2 + ab1;
x4 = b1 - ab2;
y4 = b2 + ab1;

if (BS(x3, y3) && BS(x4, y4)) sum++;
}
}

cout << sum / 4 << endl;

}

return 0;
}

＝＝＝＝＝＝hash的代码＝＝＝＝＝＝＝＝

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

#define N 40001

int n;

struct point
{
int index;//记录v的下标
point *next;
point(){index = -1; next = NULL;}
point(int i){index = i; next = NULL;}
};

struct p
{
int x, y;
}v[1001];

bool cmp(p a, p b)
{
if (a.x < b.x) return true;
if (a.x == b.x && a.y < b.y) return true;

return false;
}

bool found(point *hash, int& x, int& y)
{
int i = abs(x + y);
point *p;

if (hash[i].index == -1) return false;
p = &hash[i];
while (p != NULL)
{
if (v[p->index].x == x && v[p->index].y == y) return true;

p = p->next;
}

return false;
}

int main()
{
int i, j, sum, index, x1_x2, y1_y2, x1, y1, x2, y2;
point *p;

while (cin >> n, n)
{
point hash[N];

for (i = 0; i < n; i++) cin >> v[i].x >> v[i].y;

sort(v, v + n, cmp);

for (i = 0; i < n; i++)
{
index = abs(v[i].x + v[i].y);

if (hash[index].index == -1) hash[index].index = i;
else
{
p = &hash[index];
while (p->next != NULL) p = p->next;

p->next = new point(i);
}
}

for (sum = 0, i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (v[i].x <= v[j].x && v[i].y >= v[j].y)
{
x1_x2 = abs(v[i].x - v[j].x);

if (x1_x2 == 0) continue;

y1_y2 = abs(v[i].y - v[j].y);

x1 = v[i].x + y1_y2;
y1 = v[i].y + x1_x2;
x2 = v[j].x + y1_y2;
y2 = v[j].y + x1_x2;

if (found(hash, x1, y1) && found(hash, x2, y2)) sum++;
}
}
}

cout << sum << endl;
}

return 0;
}