C程序检测直角三角 [英] C Program to detect right angled triangles

问题描述

如果我在坐标系中给出100分，我得找如果存在这些顶点的直角三角形。
有没有办法，我能察觉这些顶点之间的直角三角形，而不必选择所有对3个顶点，然后对他们的应用勾股定理的方式？
能有这更好的算法？
感谢您的帮助。 ：）

If I am given 100 points in the coordinate system, and I have to find if there exist a right angled triangle in those vertices. Is there a way that I can detect the right angled triangle among those vertices without having to choose all pairs of 3 vertices and then applying Pythagoras theorem on them?? Can there be a better algorithm for this? Thanks for any help. :)

推荐答案

下面是一个为O（n ^ 2 log n）的-time 算法两个维度仅。我将描述什么不顺心的更高的维度。

Here's an O(n^2 log n)-time algorithm for two dimensions only. I'll describe what goes wrong in higher dimensions.

设S是集合点，其中有整数坐标。对于S中的每个点o，构建一套非零矢量V（0）= {对 - Ø| p在的S - {Ø}}和测试是否V（O）包含如下线性时间两个正交向量。

Let S be the set of points, which have integer coordinates. For each point o in S, construct the set of nonzero vectors V(o) = {p - o | p in S - {o}} and test whether V(o) contains two orthogonal vectors in linear time as follows.

方法1：每个向量（X，Y）推崇到（x / GCD（X，Y）中，y / GCD（X，Y）），其中|最大公约数（X，Y）|是，把X和Y，且其中最大公约数（X，Y）为负，如果y为负，正，如果y是正数，和最大的整数| X |如果y为零。 （这是非常相似的投入最简的分数。）关于两个维度的关键事实是，对于每一个非零向量，有正好一个典型矢量正交存在于载体中，具体地，所述封（-y，x）的。插入V（O）每个向量册封成一组数据结构，然后，在V​​（O）每个向量，仰望它的规范正交队友在该数据结构。我假设的GCD和/或一组操作需要时间O（log n）的。

Method 1: canonize each vector (x, y) to (x/gcd(x, y), y/gcd(x, y)), where |gcd(x, y)| is the largest integer that divides both x and y, and where gcd(x, y) is negative if y is negative, positive if y is positive, and |x| if y is zero. (This is very similar to putting a fraction in lowest terms.) The key fact about two dimensions is that, for each nonzero vector, there exists exactly one canonical vector orthogonal to that vector, specifically, the canonization of (-y, x). Insert the canonization of each vector in V(o) into a set data structure and then, for each vector in V(o), look up its canonical orthogonal mate in that data structure. I'm assuming that the gcd and/or set operations take time O(log n).

方法2：在媒介定义的比较如下。鉴于矢量（A，B），（C，D），写（A，B）＆LT; （C，D）当且仅当

Method 2: define a comparator on vectors as follows. Given vectors (a, b), (c, d), write (a, b) < (c, d) if and only if

s1 s2 (a d - b c) < 0,

其中，

s1 = -1 if b < 0 or (b == 0 and a < 0)
      1 otherwise
s2 = -1 if d < 0 or (d == 0 and c < 0)
      1 otherwise.

排序使用此比较的载体。 （这是非常相似的比较分数 A / B 与 C / D ）。对于每个向量（X， Y）在V（O），其正交队友二进制搜索（-y，X）。

Sort the vectors using this comparator. (This is very similar to comparing the fraction a/b with c/d.) For each vector (x, y) in V(o), binary search for its orthogonal mate (-y, x).

在三维中，该组正交于沿z轴的单位矢量矢量的是整个的x-y平面，并封相当于未能在该平面中的所有矢量映射到一个正交伴侣

In three dimensions, the set of vectors orthogonal to the unit vector along the z-axis is the entire x-y-plane, and the equivalent of canonization fails to map all vectors in this plane to one orthogonal mate.

这篇关于C程序检测直角三角的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！