#include <fstream>
using namespace std;
//-------------------------------------------int main()
{
ifstream fileIn;
fileIn.open("input.txt");
ofstream fileOut;
fileOut.open("output.txt");
int ax, ay, bx, by;
fileIn >> ax >> ay >> bx >> by;
int A1 = by-ay;
int B1 = ax-bx;
int C1 = bx*ay-ax*by;
fileIn >> ax >> ay >> bx >> by;
int A2 = by-ay;
int B2 = ax-bx;
int C2 = bx*ay-ax*by;
int det = A1*B2-A2*B1;
if(det!=0){
double x = -1.0*(C1*B2-C2*B1)/det;
double y = -1.0*(A1*C2-A2*C1)/det;
fileOut.setf(ios::scientific);
fileOut << "1 " << x << " " << y << endl;
}else{
if(A1*C2-A2*C1==0 && C1*B2-C2*B1==0) fileOut << "2" << endl;
else fileOut << "0" << endl;
}
fileIn.close();
fileOut.close();
return 0;
}
И указанное выше решение, и решение на основе разбора к задаче приводит к выполнению всех тестов, кроме №14 — "Неправильный ответ".
Используя assert , выяснил, что ошибка возникает в блоке:
if(det!=0){
double x = -1.0*(C1*B2-C2*B1)/det;
double y = -1.0*(A1*C2-A2*C1)/det;
fileOut.setf(ios::scientific);
fileOut << "1 " << x << " " << y << endl;
}
При этом вычисляются такие x и y, которые не удовлетворяют уравнениям прямых, например, |A1*x+B1*y+C1|>1e-9.
Подскажите пожалуйста, в чем проблема? Неужели есть прямые, для которых детерминант det = A1*B2-A2*B1 отличный от нуля, а точки пересечения не существует?
Здравствуйте, omgOnoz, Вы писали:
O>Зная y или x ты можешь по формуле линейного уравнения вычислить x или y.
O>x = — ( By + C ) / A
O>y = — ( Ax + c ) / B
O>Видно же, что меньше операций умножения.
В этой задаче, как и во многих других олимпиадных задачах, учитывается способ получения дейстительного числа. Вы правы, что в указанном Вами способе меньше умножений, но при этом используется приблизительный результат "х". Как следствие — "неправильный результат" в №13 и №14 тестах.
При использовании метода Крамера x и y вычисляются через целые числа, что приводит к совпадениям по всем тестам, кроме №14.
O>У тебя ошибка в формуле расчета икса. Как и в примере откуда ты копипастил.
Не могу найти ошибки.
Для х:
A1x+B1y+C1=0 и A2x+B2y+C2=0
определитель в знаменателе:
A1*B2-A2*B1
определитель в числителе
-С1*B2-B1*(-С2) = -С1*B2+B1*С2 = B1*С2-С1*B2 = -(С1*B2-B1*С2) то естть то же, что и на сайте..
если нет, то где я ошибся?
Здравствуйте, olimp_20, Вы писали:
_>Не могу найти ошибки. _>Для х: _>A1x+B1y+C1=0 и A2x+B2y+C2=0 _>определитель в знаменателе: _>A1*B2-A2*B1 _>определитель в числителе _>-С1*B2-B1*(-С2) = -С1*B2+B1*С2 = B1*С2-С1*B2 = -(С1*B2-B1*С2) то естть то же, что и на сайте.. _>если нет, то где я ошибся?
Я не уверен в каком порядке происходит преобразования int в double.
тут
double x = -1.0*(C1*B2-C2*B1)/det;
double y = -1.0*(A1*C2-A2*C1)/det;
если первым посчитается (C1*B2-C2*B1)/det и/или (A1*C2-A2*C1)/det — то получится херня (ибо целочисленное деление — остаток тю-тю).
Из примера с которого копипастил — все переменные имеют тип double.
Да и стоит ли умножать на -1.0 — не уверен, что с типом double это хорошая идея, может добавить дополнительную погрешность.
Здравствуйте, omgOnoz, Вы писали:
O>Я не уверен в каком порядке происходит преобразования int в double.
O>тут O>double x = -1.0*(C1*B2-C2*B1)/det; O>double y = -1.0*(A1*C2-A2*C1)/det; O>если первым посчитается (C1*B2-C2*B1)/det и/или (A1*C2-A2*C1)/det — то получится херня (ибо целочисленное деление — остаток тю-тю).
O>Из примера с которого копипастил — все переменные имеют тип double.
"1.0*" — специально использовано для приведения int в double (правилам приведения на С (и на С++))
Но даже, если построить монстров (с точки зрения нагромождения записей)
double x = (-1.0*(C1*B2-C2*B1))/(1.0*det);
double y = (-1.0*(A1*C2-A2*C1))/(1.0*det);
проблема с тестом №14 остается.
Поэтому остается вопрос: либо алгоритм вычисления не подходит (что очень странно), либо тест содержит какой-то частный случай (но какой??? )....
Здравствуйте, olimp_20, Вы писали:
_>"1.0*" — специально использовано для приведения int в double (правилам приведения на С (и на С++)) _>Но даже, если построить монстров (с точки зрения нагромождения записей) _>double x = (-1.0*(C1*B2-C2*B1))/(1.0*det); _>double y = (-1.0*(A1*C2-A2*C1))/(1.0*det); _>проблема с тестом №14 остается. _>Поэтому остается вопрос: либо алгоритм вычисления не подходит (что очень странно), либо тест содержит какой-то частный случай (но какой??? )....
Похоже бага в тесте, входные данные выходят за ограничение?
Координаты каждой точки — по модулю не превышающие 1000.
Ибо заменив тип коэффициентов на double — тест полностью проходит.
Видно тест валится из-за переполнения типа int — максимум и минимум коэффициентов ограничен 2 * 1000 * 1000.
Хотя тип int платформонезависимый — может на 16 битной платформе тестируют?
Здравствуйте, omgOnoz, Вы писали:
O>Похоже бага в тесте, входные данные выходят за ограничение?
O>
O>Координаты каждой точки — по модулю не превышающие 1000.
O>Ибо заменив тип коэффициентов на double — тест полностью проходит.
Действительно, если ВСЕ int заменить на double, а не только результаты вычислений.
O>Видно тест валится из-за переполнения типа int — максимум и минимум коэффициентов ограничен 2 * 1000 * 1000. O>Хотя тип int платформонезависимый — может на 16 битной платформе тестируют?
Возможно, хотя там выбор компиляторов большой... и на 32-битной int прекрасно помещается [-2млрд.; +2млрд.]
O>Скорее всего входные данные неверны.
Скорее всего хотели подловить на double, хотя потом в других задачах требуют, чтобы вычисления выполнялись максимально возможно через int...
Здравствуйте, olimp_20, Вы писали:
_> int ax, ay, bx, by;
_> int A1 = by-ay; _> int B1 = ax-bx; _> int C1 = bx*ay-ax*by;
...
_> double x = -1.0*(C1*B2-C2*B1)/det;
_>Подскажите пожалуйста, в чем проблема? Неужели есть прямые, для которых детерминант det = A1*B2-A2*B1 отличный от нуля, а точки пересечения не существует?
Здесь возможно целочисленное переролнение:
|A|<=2000
|B|<=2000
|C|<=2000000
тогда C1*B2-C2*B1 может быть больше 2^31
