ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1875. Angry Birds

Try to solve the problem WITHOUT floating numbers!
Послано 198808xc 30 янв 2012 13:57
The most important functions are listed below:

// Judge if there exist a parabola passing P[a] and P[b]
// The validation of direction of the parabola is included in the positive sign
bool Valid(int a, int b)
{
    if (P[a].x == P[b].x)
        return false;
    else return (P[a].x - P[b].x) * (P[a].x * P[b].y - P[b].x * P[a].y) > 0;
}

// Judge if the parabola passing P[a] and P[b] also passes P[c]
// Using the determinant for judgement
bool Pass(int a, int b, int c)
{
    return (P[a].x * P[a].x) * P[b].x * P[c].y +
        P[a].x * P[b].y * (P[c].x * P[c].x) +
        P[a].y * (P[b].x * P[b].x) * P[c].x -
        (P[a].x * P[a].x) * P[b].y * P[c].x -
        P[a].x * (P[b].x * P[b].x) * P[c].y -
        P[a].y * P[b].x * (P[c].x * P[c].x) == 0;
}

Note: using long integers (64-bit) to avoid overflow.

Good luck.
Re: Try to solve the problem WITHOUT floating numbers!
Послано xurshid_n 14 фев 2012 13:09
Thank you!!!
Re: Try to solve the problem WITHOUT floating numbers!
Послано ASK 2 апр 2018 18:34
Do not derive them by hand, use Maxima:

p: a*x^2+b*x=y;
s: solve([ev(p,x=x1,y=y1),ev(p,x=x2,y=y2)],[a,b])[1];
a < 0,s;

m: denom(lhs(ev(p,s,ratsimp)));
e: ev(p,s) * m, ratsimp;

to print as source code use
fortran(e);

It is also a good idea to use macro to avoid typos:

bool on_par(int a, int b, int c){ // [c] on the same parabola as [a] and [b]
# define _(a,b,c) x[c]*x[a]*(x[c]-x[a])*y[b]
  return _(a,b,c) - _(b,a,c) == _(a,c,b);
# undef _
}