是点上最大。两行？

Question

我的程序有时间问题。给定一组点，它必须说明是否所有这些点都位于两条不同的线上。

我写了代码，它在数组中有点并一个一个地删除并尝试计算它的向量。

但是这个解决方案很慢，因为它必须控制所有行的情况。输入 10,000 点需要 10 多秒。

有人可以告诉我，这里是否有更好的解决方案？

我用 Pascal 编写了这段代码：

    uses
  math;

type
  TPoint = record
    x, y: real;
  end;

  TList = array of TPoint;

function xround(value: real; places: integer): real;
var
  muldiv: real;
begin
  muldiv := power(10, places);
  xround := round(value * muldiv) / muldiv;
end;

function samevec(A, B, C: TPoint): boolean;
var
  bx, by: real; // vec A -> B
  cx, cy: real; // vec A -> C
  lb, lc: real; // len AB, len AC
begin
  bx := B.x - A.x;
  by := B.y - A.y;
  cx := C.x - A.x;
  cy := C.y - A.y;

  lb := sqrt(bx * bx + by * by);
  lc := sqrt(cx * cx + cy * cy);

  // normalize
  bx := xround(bx / lb, 3);
  by := xround(by / lb, 3);
  cx := xround(cx / lc, 3);
  cy := xround(cy / lc, 3);

  samevec := ((bx = cx) and (by = cy)) or ((bx = -cx) and (by = -cy));
end;

function remove(var list: TList; idx: integer): TPoint;
var
  i: integer;
begin
  remove.x := 0;
  remove.y := 0;
  if idx < length(list) then
    begin
      remove := list[idx];
      for i := idx to length(list) - 2 do
        list[i] := list[i + 1];
      setlength(list, length(list) - 1);
    end;
end;

var
  i, j, lines: integer;
  list, work: TList;
  A, B: TPoint;

begin
  while not eof(input) do
    begin
      setlength(list, length(list) + 1);
      with list[length(list) - 1] do
        readln(x, y);
    end;

  if length(list) < 3 then
    begin
      writeln('ne');
      exit;
    end;

  lines := 0;

  for i := 1 to length(list) - 1 do
    begin
      work := copy(list, 0, length(list));

      lines := 1;

      B := remove(work, i);
      A := remove(work, 0);
      for j := length(work) - 1 downto 0 do
        if samevec(A, B, work[j]) then
          remove(work, j);
      if length(work) = 0 then
        break;

      lines := 2;

      A := remove(work, 0);
      B := remove(work, 0);
      for j := length(work) - 1 downto 0 do
        if samevec(A, B, work[j]) then
          remove(work, j);
      if length(work) = 0 then
        break;

      lines := 3; // or more
    end;

  if lines = 2 then
    writeln('YES')
  else
    writeln('NO');
end.

谢谢，费科

附加：

program line;
{$APPTYPE CONSOLE}
uses
  math,
  sysutils;

type point=record
    x,y:longint;
  end;

label x;

var
Points,otherPoints:array[0..200001] of point;
n,n2,i,j,k,i1,i2:longint;

function sameLine(A,B,C:point):boolean;
var
  ABx,ACx,ABy,ACy,k:longint;
begin
  ABx:=B.X-A.X;
  ACx:=C.X-A.X;
  ABy:=B.Y-A.Y;
  ACy:=C.Y-A.Y;
  k:=ABx*ACy-ABy*ACx;
  if (k=0) then sameLine:=true
    else sameLine:=false;
  end;


begin
readln(n);
if (n<=4) then begin
  writeln('YES');
  halt;
  end;

for i:=1 to n do readln(Points[i].x,Points[i].y);

for i:=1 to 5 do for j:=i+1 to 5 do for k:=j+1 to 5 do if not (sameLine(Points[i],Points[j],Points[k])) then begin
  i1:=i;
  i2:=j;
  goto x;
  end;

writeln('NO');
halt; 

x:
n2:=0;
for i:=1 to n do begin
  if ((i=i1) or (i=i2)) then continue;
  if not sameLine(Points[i1],Points[i2],Points[i]) then begin
    inc(n2,1);
    otherPoints[n2]:=Points[i];
    end;
  end;

if (n2<=2) then begin
  writeln('YES');
  halt;
  end;

for i:=3 to n2 do begin
  if not sameLine(otherPoints[1],otherPoints[2],otherPoints[i]) then begin
    writeln('NO');
    halt;
    end;
  end;
writeln('YES');
end.

Answer 1

如果向量AB和AC共线或反共线，则A、B、C三点在同一条直线上。我们可以使用向量的 cross product 检查共线性 - 它应该为零。

@LU RD 已经在评论中描述了这种方法，但作者可能错过了。

请注意，该方法不会被零除 - 根本没有除法。

 ABx := B.X - A.X;
 ACx := C.X - A.X;
 ABy := B.Y - A.Y;
 ACy := C.Y - A.Y;
 Cross := ABx * ACy - ABy * ACx;
 // for integer coordinates
 if Cross = 0 then 
    A,B,C are collinear

如果坐标是浮动的，必须考虑一些公差级别。变体：

 //better if available:
 if Math.IsZero(Cross)
 if Math.SameValue(Cross, 0)
 //otherwise
 if Abs(Cross) <= SomeEpsilonValue

如果坐标范围非常大，数值误差可能很大，因此值得通过坐标差的平方幅度对公差进行归一化：

 if Math.IsZero(Cross / Max(ABx * ABx + ABy * ABy, ACx * ACx + ACy * ACy))

Answer 2

我想这个问题的答案应该分为两部分。

我。如何知道给定的三个点属于同一条直线？ Q这部分的答案是由@Lurd给出的，然后由Mbo扩展。让我们命名他们的解决方案function BelongToOneLine(Pnts: array [1..3] of TPoint): boolean;我们可以认为这部分已经解决了。

二．如何减少算法的时间消耗，或者换句话说：如何避免调用 BelongToOneLilne 以每个可能的点组合作为参数？

这是算法。

我们从任务集中 select 5 distinct 点。 5 就足够了（检查组合的可能性）。
如果给定的五个点中至少有三个点属于一条线，我们就找到了问题的答案。

if No - 那么我们不需要迭代剩余的点 - 答案是我们需要多于两行。

如果是 -（假设点 Pt1、Pt2 和 Pt3 属于同一行，而 Pt4 和 Pt5 - 不）。
然后我们将五人组中不属于线 Pt1-Pt2-Pt3 的点存储在一个不同的 "outsider" 点数组中（或存储它们的索引在主数组中）。到此步骤结束时它可能有 Length = 0。这不会影响算法的其余部分。
我们得到函数的布尔结果BelongToOneLine([Pt1, Pt2, Pt[i]]).

如果是 - 我们跳过这一点 - 它属于线 Pt1-Pt2-Pt3.

if No - 我们将这个点存储在"outsiders"数组中。
我们观察 OutsidersArray 的长度。

如果<=2那么整个Q的答案是肯定的，它们确实属于2行或更少。

if >2 然后我们迭代函数 BelongToOneLine([OutsiderPt1, OutsiderPt2, OutsiderPt[i]]) 直到 High(OutsiderArray) 或直到 OutsiderPt[i] 不属于 OutsiderPt1-OutsiderPt2 线。 OutsiderArray 的所有点必须属于同一条线，否则整个 Q 的答案将是否定的。

数学笔记

如果不进行优化，迭代次数将为 n! / ((n - k)! * k!)。通过优化它将是： 5! / ((5-3)! * 3!) + (n - 3) + P(q)outsiders * n 对于 n = 10000 大约是 15000。大多数负计数 - 大约 20000。

还有一个优化说明

用整数变量替换 TPoint 的声明。

Answer 3

搜索结果来自网络的精选片段对于 n=1：您需要两条线相交，因此最大交点数为 0。 n=2：无论维度如何，两条不同的线将始终相交至多一点。 ... 解释：每组 2 条线可以在一点相交。或者一个点是2条线的公共交点。

是点上最大。两行？

Are points on max. two lines?

delphi

geometry

pascal

line