Помощь - Поиск - Пользователи - Календарь
Полная версия: пересечение отрезков
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
milfes
Пожалуйсто помогите решить задачу:
Дано множество отрезков, заданых координатами концов. Определить количество точек пересечения.
Вот что я сам написал:

program graphpoints;
uses crt,graph;
const nmax=100;
type t_kor=record
xn,yn,xk,yk:integer;
end;
var kor:array[1..nmax] of t_kor;
i,k,n,j,y,maxx,maxy,driver,mode:integer;
r1,r2,ra,rb,r:real;

procedure generatedata;
var i:integer;
begin
for i:=1 to n do
begin
kor[i].xn:=random(maxx);
kor[i].yn:=random(maxy);
kor[i].xk:=random(maxx);
kor[i].yk:=random(maxy);
line(kor[i].xn,kor[i].yn,kor[i].xk,kor[i].yk);
end;
end;

begin
randomize;
write('Введите количество отрезков ');
readln(n);
driver:=detect;
initgraph(driver,mode,'d:\tp\bgi');
maxx:=getmaxx;
maxy:=getmaxy;
generatedata;
readkey;
closegraph;
k:=0;
for i:=1 to n-1 do
begin
for j:=i+1 to n do
begin
r1:=(kor[j].xn-kor[i].xn)*(kor[i].yk-kor[i].yn)-(kor[j].yn-kor[i].yn)*(kor[i].xk-kor[i].xn);
r:= (kor[i].yk-kor[i].yn)*(kor[j].xn-kor[j].xk)-(kor[j].yn-kor[j].yk)*(kor[i].xk-kor[i].xn);
r2:=(kor[j].xn-kor[j].xk)*(kor[j].yn-kor[i].yn)-(kor[j].yn-kor[j].yk)*(kor[j].xn-kor[i].xn);
ra:=r1/r;
rb:=r2/r;
if (ra<=1) and (ra>=0) and (rb>=0) and (rb<=1) then
k:=k+1
end;
end;
writeln('Количество точек пересечения ',k);
readkey;
end.



Программа работает неправильно, число пересечение выводится меньше, чем на самом деле.
Bokul
У тебя не правильно проверяются пересечение отрезков, глянь здесь
milfes
Спасибо, ща попробую исправить.
milfes
Вот изменил:

r1:=(kor[j].xk-kor[j].xn)*(kor[i].yn-kor[j].yn)-(kor[j].yk-kor[j].yn)*(kor[i].xn-kor[j].xn);
r:= (kor[j].yk-kor[j].yn)*(kor[i].xk-kor[i].xn)-(kor[i].yk-kor[i].yn)*(kor[j].xk-kor[j].xn);
r2:=(kor[i].xk-kor[i].xn)*(kor[i].yn-kor[j].yn)-(kor[i].yk-kor[i].yn)*(kor[i].xn-kor[j].xn);


Но результат остался прежним. mega_chok.gif
volvo
milfes, у тебя может не хватать разрядности (промежуточный результат вычисления, например, (kor[j].xk-kor[j].xn)*(kor[i].yn-kor[j].yn), не поместится в Integer, и усечется - в результате получишь неверные значения Ra, Rb) и в итоге - некорректный результат... Я бы переходил сразу на Real:

r1:=1.0 * (kor[j].xk-kor[j].xn) * 1.0 * (kor[i].yn-kor[j].yn)-
1.0 * (kor[j].yk-kor[j].yn) * 1.0 * (kor[i].xn-kor[j].xn);
r:= 1.0 * (kor[j].yk-kor[j].yn) * 1.0 * (kor[i].xk-kor[i].xn)-
1.0 * (kor[i].yk-kor[i].yn) * 1.0 * (kor[j].xk-kor[j].xn);
r2:=1.0 * (kor[i].xk-kor[i].xn) * 1.0 * (kor[i].yn-kor[j].yn)-
1.0 * (kor[i].yk-kor[i].yn) * 1.0 * (kor[i].xn-kor[j].xn);
- тогда промежуточные значения гарантированно будут в типе Real, и результат должен быть правильным... Попробуй...
milfes
Спасибо.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.