我要招人

去企业版

首页 > 试题广场 >

直角三角形的个数

[编程题]直角三角形的个数

热度指数：922 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

二维平面直角坐标系中有N个整型坐标点(x1,y1),(x2,y2),…(xN,yN)，任意三个点都可能构成一个三角形，计算这些三角形中直角三角形的个数。

输入描述:

输入有两行：
第一行为N，3≤ N ≤256
第二行为输入N个双字节整型坐标点，共2N个数据，以空格分隔横纵坐标及不同的点，x1 y1 x2 y2 … xn yn… xN yN

输出描述:

输出直角三角形个数

示例1

输入

20
0 0 0 3 1 2 3 4 5 6 7 8 1 4 2 4 3 5 5 0 5 5 2 0 2 2 3 0 3 3 4 5 6 1 3 7 4 0 5 2

输出

备注:

提示：
1、不要重复计算三角形的个数，
2、判断直角三角形用勾股定理

算法知识视频讲解

114514newnew

#include <stdio.h>

int main() {
int N;
scanf("%d", &N); // 读取点的数量
int points[256][2]; // 存储点的坐标

// 读取点的坐标
for (int i = 0; i < N; i++) {
scanf("%d %d", &points[i][0], &points[i][1]);
}

int count = 0;

// 三重循环遍历所有三点组合
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
for (int k = j + 1; k < N; k++) {
// 取三点的坐标
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int x3 = points[k][0], y3 = points[k][1];

// 计算边的向量
int dx1 = x2 - x1, dy1 = y2 - y1; // 边 AB
int dx2 = x3 - x1, dy2 = y3 - y1; // 边 AC
int dx3 = x3 - x2, dy3 = y3 - y2; // 边 BC

// 检查是否为直角三角形
if ((dx1 * dx2 + dy1 * dy2 == 0) || // AB 和 AC 直角
(dx1 * dx3 + dy1 * dy3 == 0) || // AB 和 BC 直角
(dx2 * dx3 + dy2 * dy3 == 0)) { // AC 和 BC 直角
count++;
}
}
}
}

// 输出结果
printf("%d\n", count);
return 0;
}

发表于 2024-10-26 11:05:34 回复(0)

牛客555163514号

java纯暴力无超时解法：

importjava.util.*;

publicclassMain {

publicstaticbooleanisRightAngledTriangle(int[] pointA, int[] pointB, int[] pointC) {

intax = pointA[0], ay = pointA[1];

intbx = pointB[0], by = pointB[1];

intcx = pointC[0], cy = pointC[1];

intsideAB = (ax - bx) * (ax - bx) + (ay - by) * (ay - by);

intsideBC = (bx - cx) * (bx - cx) + (by - cy) * (by - cy);

intsideCA = (cx - ax) * (cx - ax) + (cy - ay) * (cy - ay);

returnsideAB == sideBC + sideCA || sideBC == sideAB + sideCA || sideCA == sideAB + sideBC;

}

publicstaticvoidmain(String[] args) {

Scanner sc = newScanner(System.in);

intnum = sc.nextInt();

int[][] a = newint[num][2];

for(inti = 0; i < num; i++) {

a[i][0] = sc.nextInt();

a[i][1] = sc.nextInt();

}

intadd=0;

for(inti =0;i<a.length-2;i++){

for(intj =i+1;j<a.length-1;j++){

for(intk=j+1;k<a.length;k++){

if(isRightAngledTriangle(a[i],a[j],a[k])){

add++;

}

System.out.println(add);

}

发表于 2024-08-15 22:46:06 回复(0)

加麻加辣的小白很想找对象

python代码最后一个超时

def distance(x, y, nums, dis):
    if x in dis:
        if y in dis[x]:
            return dis[x][y]
    else:
        dis[x] = {}
    dis[x][y] = (nums[x][0] - nums[y][0]) ** 2 + (nums[x][1] - nums[y][1]) ** 2
    return dis[x][y]

def count(nums):
    c = 0
    dis = {}
    for x in range(len(nums)):
        for y in range(x + 1, len(nums)):
            for z in range(y + 1, len(nums)):
                edges = [distance(x, y, nums, dis), distance(x, z, nums, dis), distance(y, z, nums, dis)]
                max_dis = max(edges)
                if sum(edges) == 2 * max_dis:
                    c += 1
    return c

if __name__ == "__main__":
    N = int(input())
    nums = list(map(int, input().split(" ")))
    nums = [[nums[i * 2], nums[i * 2 + 1]] for i in range(N)]
    print(count(nums))

发表于 2024-08-13 21:54:57 回复(1)

要暴富的打工鸭很想去毕业旅行

第六个测试案例怎么会有712个结果？我算出来才596个

发表于 2024-07-19 17:21:20 回复(4)

双非小牛马hh

#include <bits/stdc++.h>
using namespace std;

long long distance(pair<int, int>A, pair<int, int>B) {
    int Ax = A.first;
    int Ay = A.second;
    int Bx = B.first;
    int By = B.second;
    long long X, Y;
    X = 1ll * (Bx - Ax) * (Bx - Ax);
    Y = 1ll * (By - Ay) * (By - Ay);
    return X + Y;
}

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i].first >> a[i].second;
    }

    int count = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j)  continue;
            for (int k = 0; k < N; k++) {
                if (i == k || j == k) {
                    continue;
                }
                long long Xij = distance(a[i], a[j]) ;
                long long Xjk = distance(a[j], a[k]) ;
                long long Xik = distance(a[i], a[k]) ;

                if (Xij == Xjk + Xik || Xjk == Xij + Xik || Xik == Xij + Xjk) {
                    count++;
                }
            }

        }
    }
    cout << count / 6;


}
// 64 位输出请用 printf("%lld")

发表于 2024-09-04 11:54:19 回复(0)

Python

啊雷洛

Python3最后一个样例超时，选PyPy3即可

def check(p1, p2, p3):

vec1 = [p1[0] - p2[0], p1[1] - p2[1]]

vec2 = [p1[0] - p3[0], p1[1] - p3[1]]

vec3 = [p2[0] - p3[0], p2[1] - p3[1]]

return (

vec1[0] * vec2[0] + vec1[1] * vec2[1] == 0 or

vec1[0] * vec3[0] + vec1[1] * vec3[1] == 0 or

vec2[0] * vec3[0] + vec2[1] * vec3[1] == 0

)

n = int(input())

data = list(map(int, input().split()))

points = [[data[i * 2], data[i * 2 + 1]] for i in range(n)]

ans = 0

for i in range(n):

for j in range(i + 1, n):

for k in range(j + 1, n):

if check(points[i], points[j], points[k]):

ans += 1

print(ans)

编辑于 2024-08-30 13:53:44 回复(0)

C/C++

huixu

#include <iostream>
#include <vector>
using namespace std;

// 定义一个点的结构体
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
};

// 计算两个向量是否垂直
bool isRightAngle(Point a, Point b, Point c) {
int ab_x = b.x - a.x;
int ab_y = b.y - a.y;
int ac_x = c.x - a.x;
int ac_y = c.y - a.y;
int bc_x = c.x - b.x;
int bc_y = c.y - b.y;

return (ab_x * ac_x + ab_y * ac_y == 0) ||
(ab_x * bc_x + ab_y * bc_y == 0) ||
(ac_x * bc_x + ac_y * bc_y == 0);
}

int countRightTriangles(vector<Point>& points) {
int n = points.size();
int count = 0;

// 三重循环枚举每个点的组合
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (isRightAngle(points[i], points[j], points[k])) {
count++;
}
}
}
}
return count;
}

int main() {
int N;
cin >> N;

vector<Point> points;
for (int i = 0; i < N; ++i) {
int x, y;
cin >> x >> y;
points.emplace_back(x, y);
}

int result = countRightTriangles(points);
cout << result << endl;

return 0;
}

发表于 2024-08-05 22:43:21 回复(0)

提交观点

问题信息

难度：

7条回答 32收藏 1326浏览

直角三角形的个数

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题