简答题
偏难
#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 <bits/stdc++.h>
using namespace std;
int t, n, ans;
struct node
{
int x, y;
} a[55];
vector<node> v;
bool cmp(node x, node y)
{
if (x.x != y.x)
return x.x < y.x;
return x.y < 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 >> t;
while (t--)
{
cin >> n;
ans = 0;
v.clear();
for (int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1, cmp);
v.push_back(a[1]);
for (int i = 2; i <= 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 < v.size() - 3; i++)
{
for (int j = i + 1; j < v.size() - 2; j++)
{
for (int k = j + 1; k < v.size() - 1; k++)
{
for (int w = k + 1; w < v.size(); w++)
{
if (dist(v[i], v[w]) == dist(v[j], v[k]) && (v[i].y == v[k].y) && (v[i].x == v[j].x) && (v[k].x == v[w].x))
{
ans++;
}
}
}
}
}
cout << ans << "\n";
}
return 0;
}</pre>
这道题暂未补解析。