Squares（枚举+set 查找）

http://poj.org/problem?id=2002

题意：给出n组坐标，判断这些坐标能组成的正方形的个数。

思路：参考某大神的想法，先枚举两个点，然后利用公式表示出另外两个点，判断这两个点是否在这n组坐标中,其中查找另两个坐标用的set容器。

已知 (x1,y1)(x2,y2);

则：x3 = x1+(y1-y2); y3 = y1 -(x1-x2);

x4 = x2 +(y1-y2);y4 = y2 -(x1-x2);

或：x3 = x1 -(y1-y2);y3 = y1+(x1-x2);

x4 = x2 -(y1-y2);y4 = y2 +(x1-x2);

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <set>

 const int N=;

 const int maxn=;

 using namespace std;

 struct node

 {

     long long  x;

     long long  y;

 } p[maxn];

 int main()

 {

     int n;

     while(~scanf("%d",&n)&&n)

     {

         int ans = ;

         set<long long>tt;

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

         {

             scanf("%lld %lld",&p[i].x,&p[i].y);

             tt.insert(p[i].x*N+p[i].y);//将坐标转化成一个数，坐标不同，则这个数就不同

         }

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

         {

             int x1 = p[i].x;

             int y1 = p[i].y;

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

             {

                 int x2 = p[j].x;

                 int y2 = p[j].y;

                 int x3 = x1+(y1-y2);

                 int y3 = y1-(x1-x2);

                 int x4 = x2+(y1-y2);

                 int y4 = y2-(x1-x2);

                 if (tt.count(x3*N+y3) && (tt.count(x4*N+y4)))// 查找坐标是否存在

                     ++ans;

                 x3 = x1-(y1-y2);

                 y3 = y1+(x1-x2);

                 x4 = x2-(y1-y2);

                 y4 = y2+(x1-x2);

                 if (tt.count(x3*N+y3) && (tt.count(x4*N+y4)))

                     ++ans;

             }

         }

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

     }

     return ;

 }

巴特西

Squares（枚举+set 查找）

最新文章

热门文章