Задача на геометрию

[k1r1ch]

Помогите с задачкой:
http://acmp.ru/?main=task&id_task=12
Была идея находить центр прямоугольника (XС = (X1 + X4) / 2; YС = (Y2 + Y3) / 2), а потом проверять, пересекается ли отрезок (XC,YC)(X,Y) и каждый из четырех отрезков-сторон прямоугольника. Если есть хоть одно пересечение, тогда неудачное приземление. X1, X2, X3, X4, Y1, Y2, Y3, Y4 - координаты прямоугольника, XC, YC - позиция центра, X, Y - координаты приземления. Но застрял на нахождении пересечения отрезков. Как это сделать? А может вообще идея не верная?

[LeBron]

Если обозначить прямоугольник АВСD, а точку приземления К, то К принадлежи прямоугольнику, если равны площадь ABCD и сумма площадей KAB, KВC, KDC, KАD. При этом К находится строго внутри (не на границе) в том случае, если площади всех 4 треугольников ненулевые.
Это мое решение.
Ваше решение тоже верное, только оно мне кажеться более сложным в плане "придумывания реализации" и в плане теории вообще. Что бы проверить, пересекаються ли отрезки АВ и СD, надо проверять через векторное произведение, находяться ли А и В по разные стороны от СD и находяться ли С и D по разные стороны от АВ (надо смотреть на знак ориентированой площади построенных на векторах треугольников). Можете потренироваться, на АСМП есть задача, которая так и называеться - "пересечение отрезков". Только у нее сложность выше на несколько процентов по сравнению с этой.
На будущее - не там создаете темы. Такий теме место в помощи студентам.

[ОДИНОЧЕСТВО В СЕТИ]

рассматривай 4 треугольника (x2y2,x1y1,xy) (x4y4,x1y1,xy) (x2y2,x3y3,xy)
(x4y4,x3y3,xy) если их общая площадь равна сумме площадей треугольников (x2y2,x1y1,x4y4) и (x2y2,x4y4,x3y3) значит приземлился на участке если нет то не попал!
//чуть не успела!

[k1r1ch]

Так, пролистал учебник по геометрии вперед, нашел, что площадь треугольника = основание * высота / 2. Сейчас попробую...
Да, мой вариант был страшный . Попытался по Википедии понять, что такое вектор, понял только, что это отрезок с направлением
З.Ы.: А почему в Помощь студентам? Там же вроде задачки учебные, а тут ну... не учебная задача

[ОДИНОЧЕСТВО В СЕТИ]

площадь треугольника = основание * высота / 2

проще формулой герона воспользоваться

[k1r1ch]

Площадь можно найти по формуле Герона:
S = sqrt( p (p-a) (p-b) (p-c) )
S - площадь
sqrt - квадратный корень
p = (a+b+c) / 2 - полупериметр
a, b, c - стороны
Поделив удвоенную площадь на одну из сторон получим высоту, опущенную на эту сторону

Нашел в нете. Щас попробую...

[LeBron]

Сообщение от k1r1ch

Так, пролистал учебник по геометрии вперед, нашел, что площадь треугольника = основание * высота / 2. Сейчас попробую...
Да, мой вариант был страшный . Попытался по Википедии понять, что такое вектор, понял только, что это отрезок с направлением
З.Ы.: А почему в Помощь студентам? Там же вроде задачки учебные, а тут ну... не учебная задача

Задача учебная. Она не несет в себе никакой олимпиадной ценности. Даже та задача на динамику с ИОИ1996 была на порядок сложнее. Такое даже на области школьникам давать слишком просто. Сдесь главное, что может отпугивать - при кривых руках довольно много кода получаеться, я выдел реализацию на 4500 символов
По поводу площади - Ваша находка может быть использована только в векторке. Вообще, нормальное нахождение площади треугольника по координатам вершин - это Героном.
Ну а задача к разделу не привязана, так как нету наработок на конкретном языке, и самой привязаности к языку (Вы ведь не будуте против, если Вам решение на плюсах дать?). Фактически, Вы не требуете кода, только алго, так что нету привязанности ни к одному языку.

[k1r1ch]

Да... Извиняйте за глупые вопросы, но я в физико-химическом классе учусь, поэтому не особо люблю геометрию... Чтобы найти длину стороны, нашел формулу:

sqrt(sqr(x2-x1)+sqr(y2-y1))

Почему это так? Вроде это как-то из Пифагора следует, но как, не пойму!

[ОДИНОЧЕСТВО В СЕТИ]

а ты нарисуй в координатной сетке свои 2 точки и отрезок их соединяющии и все поймешь

[k1r1ch]

Вот, накалякал код, но он не хочет работать че-то! В принципе то написано правильно?
2LeBron: Видите ли, у меня именно с задачами на геометрию напряг . Пытаюсь это исправить...

program ACMP_12;
const
  Fst: array [1..4] of integer = (1, 2, 1 ,3);
  Snd: array [1..4] of integer = (2, 3, 3, 4);
var
  XG, YG, A, B, C, P, S, SR: extended;
  N, i, j, Counter: integer;
  X, Y: array [1..4] of extended;
  Txt: Text;

begin
  Assign(Txt, 'Input.txt'); Reset(Txt);
  Read(Txt, N); Counter := 0;
  for i := 1 to N do
  	begin
      Read(Txt, XG, YG, X[1], Y[1], X[2], Y[2], X[3], Y[3], X[4], Y[4]);
      S := 0;
      SR := Sqrt(Sqr(X[2] - X[1]) + Sqr(Y[2] - Y[1])) *
      Sqrt(Sqr(X[3] - X[1]) + Sqr(Y[3] - Y[1]));
      for j := 1 to 4 do
      	begin
        	A := Sqrt(Sqr(X[Fst[i]] - X[Snd[i]]) + Sqr(Y[Fst[i]] - Y[Snd[i]]));
      		B := Sqrt(Sqr(XG - X[Fst[i]]) + Sqr(YG - Y[Fst[i]]));
      		C := Sqrt(Sqr(XG - X[Snd[i]]) + Sqr(YG - Y[Snd[i]]));
     		  P := (A + B + C) / 2;
      		S := S + Sqrt(P * (P - A) * (P - B) * (P - C));	
        end;
      if SR = S then Inc(Counter);
    end;
  Close(Txt);
  Assign(Txt, 'Output.txt'); Rewrite(Txt);
  Write(Txt, Counter); Close(Txt);
end.