简答题 偏难
#7312

矩形数量 给出平面上一些点(少于50个),坐标都是整数(|x i |,|y i | <= 109),有可能重复。问存在多少个以这些点为顶点的平行于坐标轴的不同矩…

矩形数量

给出平面上一些点(少于50个),坐标都是整数(|xi|,|yi| <= 109),有可能重复。问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。(两个矩形如果四个顶点坐标都相同,就算相同的矩形)

时间限制:1000

内存限制:65536

输入

第一行一个整数T(T <= 100)表示测试数据的组数 对于每组数据 第一行一个整数n,表示点的数量 下面n行每行两个整数xi,yi表示点的坐标

输出

T行,每行一个整数表示以这些点为顶点的平行于坐标轴的矩形个数

样例输入

1
7
0 0
0 1
0 2
1 0
1 1
1 2
0 0

样例输出

3

提示

直接穷举即可。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int t, n, ans; struct node {     int x, y; } a[55]; vector&lt;node&gt; v; bool cmp(node x, node y) {     if (x.x != y.x)         return x.x &lt; y.x;     return x.y &lt; y.y; } long long dist(node x, node y) {     return (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y); } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cin &gt;&gt; t;     while (t--)     {         cin &gt;&gt; n;         ans = 0;         v.clear();         for (int i = 1; i &lt;= n; i++)             cin &gt;&gt; a[i].x &gt;&gt; a[i].y;         sort(a + 1, a + n + 1, cmp);         v.push_back(a[1]);         for (int i = 2; i &lt;= n; i++)         {             if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y)                 v.push_back(a[i]);         }         for (int i = 0; i &lt; v.size() - 3; i++)         {             for (int j = i + 1; j &lt; v.size() - 2; j++)             {                 for (int k = j + 1; k &lt; v.size() - 1; k++)                 {                     for (int w = k + 1; w &lt; v.size(); w++)                     {                         if (dist(v[i], v[w]) == dist(v[j], v[k]) &amp;&amp; (v[i].y == v[k].y) &amp;&amp; (v[i].x == v[j].x) &amp;&amp; (v[k].x == v[w].x))                         {                             ans++;                         }                     }                 }             }         }         cout &lt;&lt; ans &lt;&lt; "\n";     }     return 0; }</pre>
这道题暂未补解析。