2 条题解
-
4
本题做法就是暴力枚举,因为数据范围都比较小。可以尝试这个操作。
暴力枚举当然是一次性枚举4个点的坐标,然后判断这4个点能否构成矩形,同时判断是否可以平行坐标轴即可。
首先题目说了有可能有重复的点,那我们需要排序后去重,同时排序也是为了方便我们枚举4个点。
排序去重应该很好理解,按照进行排序,相等按照排序,都是从小到大。
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; } 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]); }
然后开始4个循环暴力枚举,如何判断4个点能否构成矩形,根据我们排序后的坐标,选取4个坐标一定是满足如下条件。
,
,
假设这4个点已经可以构成矩形,
那么它们一定是这个样子。
所以我们根据初中学的几何知识,对角线相等的一定是矩形,也就是
接下来继续搞定它何时可以垂直坐标轴,那么显然
即可。
#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
-
-3
写题解请注意 鼓励大家写题解,但注意题解格式。
题解一定要有思路解析或代码注释,能否让别人理解你的思路
也是你的能力的检验,不要只放无意义的代码给大家复制,那就失去了做题的初心。
给代码两端加上这个会舒服一些
```cpp
你的代码
```
</span>
这个点在键盘的左上角tab上面那个键,注意切换输入法
#include<iostream> using namespace std; int main() { int n; cin>>n;//这是一个注释 return 0; }
请注意严禁抄袭题解,写题解不要只放代码,需加上你的思路或代码注释。
抄袭题解一经发现直接取消成绩。
题解被删除的可能
- 代码不符合格式规范
- 没有思路讲解或者没有注释,
- 无意义的题解
大家携手共同维护一个良好的编程环境,如果一经发现,多次作乱。可能会被管理员拉黑,请注意,一旦拉黑即失去登陆资格。
- 1
信息
- ID
- 193
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 347
- 已通过
- 82
- 上传者