链接:https://ac.nowcoder.com/acm/contest/59840/K 来源:牛客网 给定 � n 个坐标,求其中 3 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形,等边三角形为特殊的等腰三角形。
时间: 2023-12-30 13:04:42 浏览: 53
这道题可以用哈希表来解决。首先枚举三角形的顶点,然后计算出这个顶点到其它点的距离,并将距离存入哈希表中。接着枚举其它点作为三角形的另一个顶点,计算出这个点到剩下的点的距离,并在哈希表中查找是否存在与之前顶点距离相等的点,如果存在,则说明这三个点可以组成等腰三角形。
具体实现可以使用 STL 中的 unordered_map 来实现哈希表。时间复杂度为 O(n^2)。
以下是代码实现:
相关问题
链接:https://ac.nowcoder.com/acm/contest/59840/K 来源:牛客网 给定 � n 个坐标,求其中 3 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形,等边三角形为特殊的等腰三角形。
这道题可以通过枚举任意三个点,判断它们能否组成等腰三角形来解决。具体方法是,计算其中两个点的距离,然后枚举第三个点,判断其与这两个点的距离是否相等。如果相等,则找到了一个等腰三角形。
需要注意的是,同一个等腰三角形可能会被多次计算,因此需要使用一些方法来避免重复计算。一种常用的方法是,对所有点按照横坐标排序,然后枚举每个点作为等腰三角形的中点,再枚举与该点横坐标相差不超过距离的点作为另外一个顶点,这样可以避免重复。
时间复杂度为 O(n^2 log n),可以通过本题。
https://ac.nowcoder.com/acm/contest/67743/L
很抱歉,我无法访问互联网上的链接。但是,我可以为您提供一些关于Nowcoder的一般信息。
Nowcoder是一个面向程序员的在线学习和竞赛平台,提供各种编程题目和算法竞赛。链接中的https://ac.nowcoder.com/acm/contest/67743/L可能是一个Nowcoder的竞赛链接,其中的"/acm/contest/67743/L"可能是竞赛的具体页面或题目链接。
如果您对Nowcoder平台或者竞赛有任何具体问题,我会尽力回答。请提出您的问题。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)