Помогите у меня обл. олимпиада через неделю никак не могу понять как нормальным способом узнать пересекаются ли прямые или отрезки, срочно желательно напишите программку

| Сообщение посчитали полезным:

y=kx+b уравнение прямой
Если k первой прямой равен k второй прямой то линии паралельный => не перескаются
ЗЫ. Открой учебник по геометрии за 5 класс

| Сообщение посчитали полезным:

На счет прямых:
Первая задана уравнением: y1=ax1+b
Вторая: y2=cx2+d
Если прямые пересекаются, значит в этой точке y1=y2, x1=x2

Привоим все в систему
y=ax+b
y=cx+d

Получается, точка пересечения будет тут:
x = (d-b)/(a-c) (y - сам посчитаешь)

Не пересекаюся если a=c

Топегспартер, тебе не на олимпиаду надо, а в школу почаще ходить...

| Сообщение посчитали полезным:

Ну и как это относится к тематике данного форума? Эту тему ПОКА не закрываю, хотя явный кандидат на закрытие, подобные темы надо постить на форумах для программистов на паскале.

| Сообщение посчитали полезным:

На счет отрезков, строить по координатам уравнение прямой, вычисляешь точку пересечения, потом проверяешь, принадлежит ли она обоим отрезкам!

| Сообщение посчитали полезным:

Пересечение отрезков http://program.rin.ru/cgi-bin/print.pl?id=646
Вообще погуглил 5 минут и вся инфа у тебя в кармане.
Печально.... ничего не скажешь...

-----
Я ещё не волшебник, я только учусь...

| Сообщение посчитали полезным:

Типа все такие умные ) закрывайте тему, спасибо, что не помогли, вообще-то в программировании все геометрические фигуры задаются координатами вершин, и никакие коэффициенты там неизвестны, а как найти их заминимальное кол-во тактов никто не сказал, а через условия if относильльно вершин не самый эффективный метод, тут через векторы нужно, но я никак не могу понять как, а насчет вычислять точку пересечения и смотреть принадлежит ли она обоим отрезкам вопрос: как заставить программу это сделать? перебор тут не сильно поможет имхо иррацанальные и корни

| Сообщение посчитали полезным:

AC а ты не наезжай, как задал вопрос, так на него и ответили.

-----
Yann Tiersen best and do not fuck

| Сообщение посчитали полезным:

AC пишет:
а насчет вычислять точку пересечения и смотреть принадлежит ли она обоим отрезкам вопрос: как заставить программу это сделать?

координаты одного отрезка (x1, y1) (x2, y2)
если точка пересечения (x, y)
то принадлежность точки отрезку проверяешь вот так:
if (x in [x1..x2]) and (y in [y1..y2]) then
// Точка принаждежит отрезку
Уж проверку на то что x1 должен быть меньше x2 и тоже самое с у - сделаешь сам.
А вот если ты не знаешь как их двух вершин отрезка построить уравнение прямой, то тебе точно на олимпиаду ходить нельзя!

| Сообщение посчитали полезным:

Enigma пишет:
координаты одного отрезка (x1, y1) (x2, y2)
если точка пересечения (x, y)
то принадлежность точки отрезку проверяешь вот так:
if (x in [x1..x2]) and (y in [y1..y2]) then
// Точка принаждежит отрезку
Уж проверку на то что x1 должен быть меньше x2 и тоже самое с у - сделаешь сам.
А вот если ты не знаешь как их двух вершин отрезка построить уравнение прямой, то тебе точно на олимпиаду ходить нельзя!
мне можно ) уравнение могу построить, но кажется есть способ который кроме координат ничего не требует, то есть условие поиска без коэффициентов, при котором минимальное кол-во операций

| Сообщение посчитали полезным:

AC пишет:
вычислять точку пересечения и смотреть принадлежит ли она обоим отрезкам вопрос: как заставить программу это сделать? перебор тут не сильно поможет имхо иррацанальные и корни
Какой в жопу перебор?
Какую тебе олимпиаду???
AC пишет:
тут через векторы нужно
тут можно и без векторов... но уж если очень хочецца, то вот через них
точка A(x,y) отрезок с концевыми точками B(x1,y1) и C(x2,y2)
Точки отрезка z можно описать уравнением
pOB+(1-p)OC=z, 0<=p<=1, OB и OC - векторы.
Если существует такое p, 0<=p<=1, что
pOB+(1-p)OC=A,
то A лежит на отрезке, иначе - нет.
Равенство (*) расписывается по координатно так:
px1+(1-p)x2=x
py1+(1-p)y2=y
Из первого уравнения находим p, подставляем во второе: если получаем равенство и
0<=p<=1, то A на отрезке, иначе - нет.
PS: я бы на твоём месте на олимпиаду не ехал ;)

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

| Сообщение посчитали полезным:

Enigma пишет:
if (x in [x1..x2]) and (y in [y1..y2]) then
не знаю как в других языках, но в Delphi это глючить будет, если x2,y2 не уложутся в байт
лучше in не использовать... он работает [0..255]

AC тебе вообще для 2D или для 3D надо?

--> маленький ликбез <-- http://faqs.org.ru/science/geometry_faq.htm на будущее

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

| Сообщение посчитали полезным:

ох уж эти юные дарования
algolist.manual.ru/maths/geom/intersect/lineline2d.php

-----
Недостаточно только получить знания:надо найти им приложение

| Сообщение посчитали полезным:

Вот кусок моей реализации:

X11 – X первой точки первого отрезка
X12 – X второй точки первого отрезка

X21 – X первой точки второго отрезка
X22 – X второй точки второго отрезка

#define EPSYLON 1E-16

bool IsCrossing( ....)
{
long idx2;
bool bRes = false;
double delta;
double D[3] = { X12 – X11, Y12 – Y11, Z12 – Z11};
double E[3] = { X22 – X21, Y22 – Y21, Z22 – Z21};
for ( long idx1 = 0; idx1 < 3; idx1++)
{
if (idx1 < 2) idx2 = ( idx1 + 1) % 3;
delta = E[idx1] * D[idx2] - E[idx2] * D[idx1];
if ( fabs( delta) > EPSYLON)
{
bRes = true;
break;
}
}
return bRes;
}

| Сообщение посчитали полезным:

AC, неделя прошла. Как там олимпиада, выиграл?

| Сообщение посчитали полезным: