学步园

quares

题意比较简单，就是在一堆点用找能组成正方形的点，看能找出多少组。

开始没思路，怕超时。上网找了找，基本思路是枚举两个点，查找另外两个看存不存在。这个就是简单的几何，因为点是排过序的，我们只需要找到两个点在左面（如果y值一样就在下面）的情况，但这样还会多算一遍，因为一个正方形要有两条边在左面（或一条左一条下），所以要除以2。

查找有用二分查找的，有用hash的。因为stl里有二分查找函数，所以好写些。

#include <iostream><br /> #include <cstring><br /> #include <cmath><br /> #include <cstdlib><br /> #include <algorithm><br /> #include <string><br /> #include <cstdio><br /> #include <climits><br /> #include <queue><br /> #include <map><br /> #include <list><br /> #include <vector><br /> using namespace std;<br /> struct node<br /> {<br /> int x, y;<br /> } p[1001];<br /> bool op(const struct node &xx, const struct node &yy)<br /> {<br /> if (xx.x == yy.x)<br /> return xx.y < yy.y;<br /> else<br /> return xx.x < yy.x;<br /> }<br /> int main()<br /> {<br /> int points;<br /> while (scanf("%d", &points), points)<br /> {<br /> int sum = 0;<br /> for (int i = 0; i < points; ++i)<br /> scanf("%d%d", &p[i].x, &p[i].y);<br /> sort(p, p + points, op);<br /> for (int i = 0; i < points; ++i)<br /> {<br /> for (int j = i + 1; j < points; ++j)<br /> {<br /> node p0, p1;<br /> p0.x = p[i].x + p[j].y - p[i].y;<br /> p0.y = p[i].y + p[i].x - p[j].x;<br /> p1.x = p[j].x + p[j].y - p[i].y;<br /> p1.y = p[j].y + p[i].x - p[j].x;<br /> if (!binary_search(p, p+points, p0, op))<br /> continue;<br /> if (!binary_search(p, p+points, p1, op))<br /> continue;<br /> sum++;<br /> }<br /> }<br /> printf("%d/n", sum / 2);<br /> }<br /> return 0;<br /> }

时间1.5s多

刚才突然想到用set写，结果用时2.6s多……

#include <iostream><br /> #include <cstring><br /> #include <cmath><br /> #include <cstdlib><br /> #include <algorithm><br /> #include <string><br /> #include <cstdio><br /> #include <climits><br /> #include <queue><br /> #include <map><br /> #include <set><br /> #include <vector><br /> using namespace std;<br /> struct node<br /> {<br /> int x, y;<br /> friend bool operator<(const node &a, const node &b)<br /> {<br /> if (a.x == b.x)<br /> return a.y < b.y;<br /> else<br /> return a.x < b.x;<br /> }<br /> };<br /> int main()<br /> {<br /> int points;<br /> while (scanf("%d", &points), points)<br /> {<br /> int sum = 0;<br /> set<node> s;<br /> for (int i = 0; i < points; ++i)<br /> {<br /> node tmp;<br /> scanf("%d%d", &tmp.x, &tmp.y);<br /> s.insert(tmp);<br /> }</p> <p> set<node>::iterator ita, itb;<br /> for (ita = s.begin(); ita != s.end(); ita++)<br /> {<br /> for (itb = ita; itb != s.end(); itb++)<br /> {<br /> if (ita == itb)<br /> continue;<br /> node p0, p1;<br /> p0.x = ita->x + itb->y - ita->y;<br /> p0.y = ita->y + ita->x - itb->x;<br /> p1.x = itb->x + itb->y - ita->y;<br /> p1.y = itb->y + ita->x - itb->x;<br /> if (s.find(p0)== s.end())<br /> continue;<br /> if (s.find(p1)==s.end())<br /> continue;<br /> sum++;<br /> }<br /> }<br /> printf("%d/n", sum / 2);<br /> }<br /> return 0;<br /> }

后来发现可以一个正方形只算一次，时间降到了700ms+

#include <iostream><br /> #include <cstring><br /> #include <cmath><br /> #include <cstdlib><br /> #include <algorithm><br /> #include <string><br /> #include <cstdio><br /> #include <climits><br /> #include <queue><br /> #include <map><br /> #include <list><br /> #include <vector><br /> using namespace std;<br /> struct node<br /> {<br /> int x, y;<br /> } p[1001];<br /> bool op(const struct node &xx, const struct node &yy)<br /> {<br /> if (xx.x == yy.x)<br /> return xx.y < yy.y;<br /> else<br /> return xx.x < yy.x;<br /> }<br /> int main()<br /> {<br /> int points;<br /> while (scanf("%d", &points), points)<br /> {<br /> int sum = 0;<br /> for (int i = 0; i < points; ++i)<br /> scanf("%d%d", &p[i].x, &p[i].y);<br /> sort(p, p + points, op);<br /> for (int i = 0; i < points; ++i)<br /> {<br /> for (int j = i + 1; j < points; ++j)<br /> {<br /> if (p[i].x <= p[j].x && p[i].y >= p[j].y)<br /> {<br /> node p0, p1;<br /> p0.x = p[i].x + p[j].y - p[i].y;<br /> p0.y = p[i].y + p[i].x - p[j].x;<br /> p1.x = p[j].x + p[j].y - p[i].y;<br /> p1.y = p[j].y + p[i].x - p[j].x;<br /> if (!binary_search(p, p+points, p0, op))<br /> continue;<br /> if (!binary_search(p, p+points, p1, op))<br /> continue;<br /> sum++;<br /> }<br /> }<br /> }<br /> printf("%d/n", sum);<br /> }<br /> return 0;<br /> }