gpt4 book ai didi

delphi - 是最大的点。两条线?

转载 作者:行者123 更新时间:2023-12-03 18:40:06 24 4
gpt4 key购买 nike

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

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

但是这个解决方案很慢,因为它必须控制所有行的情况。输入 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.

最佳答案

如果向量 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

如果坐标是 float 的,则必须考虑某种容差水平。变体:
 //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))

关于delphi - 是最大的点。两条线?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46715400/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com