自己注册公司网站,企业组织架构图,校园时空网站建设分析,昆明网站建设王道下拉棒题目#xff1a;#xff08;数三角#xff09;
题目描述#xff08;14届 CC B组E题#xff09; 解题思路#xff1a;
给定 n 个点的坐标#xff0c;计算其中可以组成 等腰三角形 的三点组合数量。 核心条件#xff1a;等腰三角形的定义是三角形的三条边中至少有…题目数三角
题目描述14届 CC B组E题 解题思路
给定 n 个点的坐标计算其中可以组成 等腰三角形 的三点组合数量。 核心条件等腰三角形的定义是三角形的三条边中至少有两条边的长度相等。 坐标平面上的三点是否共线如果三点共线它们无法组成三角形。该程序在计算三点组合时会排除共线的情况。 解决方案对于每个点 i计算它与其他点之间的距离并将具有相同距离的点分组保存在一个映射表map中。随后从每组具有相同距离的点中组合出两个点构成一个等腰三角形。
代码实现C
#include bits/stdc.h
using namespace std;
using ll long long;
using pll pairll, ll;
double dis(ll x1, ll y1, ll x2, ll y2){return pow((x1 - x2), 2) pow((y1-y2),2);
}
bool check(pll p1, pll p2, pll p3){//判断是否三点共线if(p1.second p2.second || p1.second p3.second) return p1.second p2.second p1.second p3.second;double a (p1.first - p2.first) * 1.0 / (p1.second-p2.second);double b (p1.first - p3.first) * 1.0 / (p1.second-p3.second);return abs(a - b) 1e-6;
}
int main() {ll n; cin n;vectorpll arr;for (int i 0; i n; i) {ll x, y;cin x y;arr.emplace_back(x, y);}ll ans 0;//equ[i]存储的是第i个点所对应的map表//map表的含义是 有哪些点到第i个点的距离为key这些点的下标用一个vector收集vectormapdouble,vectorint equ(n);for(int i 0; i n; i){auto m equ[i];for(int j 0; j n; j){//遍历其他的所有点在map中记录相等距离if(i ! j){pll p1 arr[i]; pll p2 arr[j];double d dis(p1.first,p1.second,p2.first,p2.second);m[d].push_back(j);}}//收集完成之后遍历这张map表for(const auto [k,v] : m){for(int a 0; a v.size(); a){ //从到当前点的距离相等的点之中选取两个点abfor(int b a 1; b v.size(); b){if(!check(arr[i],arr[v[a]],arr[v[b]])){//只要不是三点共线ans;}}}}}cout ans;
} 得到运行结果 代码分析 距离计算dis 函数计算两个点之间的欧几里得距离的平方这样可以避免使用浮点运算。 三点共线判断check 函数通过检查斜率是否相等来判断三点是否共线。通过分段计算和比较斜率来避免浮点数精度误差。 构建距离映射对于每个点 iii计算它到其他点的距离并使用 map 将这些距离相等的点分组。 等腰三角形组合计数从距离相等的点中选择两个不同的点与当前点 iii 组合成三角形检查是否共线。若不是共线则计数增加。 难度分析
⭐️⭐️⭐️⭐️ 总结 时间复杂度该算法的复杂度为 因为它使用三重循环来枚举所有三点组合。 空间复杂度使用了 map 来存储每个点到其他点的距离信息相应的空间复杂度为 。
