A45698. 矩形数量给出平面上一些点(少于 50 个） ， 坐标都是整数(|xi|,|yi| <= 109)， 有可能重复。 问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。(两个矩形如果四个顶点坐标都相同， 就算相同的矩形)输入第一行一个整数 T(T <= 100)表示测试数据的组数 对于每组数据 第一行一个整数 n， 表示点的数量 下面 n 行每行两个整数 xi,yi 表示点的坐标输出T 行， 每行…
填空题
中等
知识点
题目描述
矩形数量
给出平面上一些点(少于 50 个） ， 坐标都是整数(|xi|,|yi| <= 109)， 有可能重复。 问存在多少个以这些点为顶点的平行于坐标轴的不同矩形。
(两个矩形如果四个顶点坐标都相同， 就算相同的矩形)
输入
第一行一个整数 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
提示
直接穷举即可。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>//后面调用sort排序函数
using namespace std;
int t, n, ans;
struct node
{
int x, y;
}
a[55];
vector<node> v;//动态数组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;
}
上一题
下一题