Я всегда думал, что в стандартных библиотеках все хорошо протестировано и работает безупречно. Моему удивлению не было предела, когда я увидел какие результаты выдал следующий код.
java.awt.geom
Class Line2D
ptLineDist
public static double ptLineDist(double X1,
double Y1,
double X2,
double Y2,
double PX,
double PY)
Returns the distance from a point to a line. The distance measured is the distance between the specified point and the closest point on the infinitely-extended line defined by the specified coordinates. If the specified point intersects the line, this method returns 0.0.
System.out.println(Line2D.ptLineDist(0, 0, 1, 200, 1, 199));
System.out.println(Line2D.ptLineDist(0, 0, 1, 2000, 1, 1999));
System.out.println(Line2D.ptLineDist(0, 0, 1, 20000, 1, 19999));
System.out.println(Line2D.ptLineDist(0, 0, 1, 200000, 1, 199999));
System.out.println(Line2D.ptLineDist(0, 0, 1, 2000000, 1, 1999999));
System.out.println(Line2D.ptLineDist(0, 0, 1, 20000000, 1, 19999999));
0.004999937545118085
5.000601076713239E-4
0.0 --- расстояние от точки (1,19999) до прямой (0,0) (1, 20000) равно 0 !!!
0.0
0.0
0.25 --- откуда здесь 0.25 ???
Кто может обьяснить такие странные результаты?
import java.awt.geom.*;
public class test
{
public static void main( String[] args )
{
System.out.println( new Line2D.Double( 0.0, 0.0, 1.0, 200.0 ).ptSegDist( 1.0, 199.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 1.0, 2000.0 ).ptSegDist( 1.0, 1999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 1.0, 20000.0 ).ptSegDist( 1.0, 19999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 1.0, 200000.0 ).ptSegDist( 1.0, 199999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 1.0, 2000000.0 ).ptSegDist( 1.0, 1999999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 1.0, 20000000.0).ptSegDist( 1.0, 19999999.0 ) );
}
}
0.004999937501174908
4.999999375293843E-4
4.9999999848063224E-5
5.000000206850923E-6
5.000222246516501E-7
5.053229617420784E-8
Еще лучше
System.out.println( new Line2D.Double( 1.0, 200.0 ,0.0, 0.0).ptSegDist( 1.0, 199.0 ) );
System.out.println( new Line2D.Double( 1.0, 2000.0 ,0.0, 0.0).ptSegDist( 1.0, 1999.0 ) );
System.out.println( new Line2D.Double( 1.0, 20000.0 ,0.0, 0.0).ptSegDist( 1.0, 19999.0 ) );
System.out.println( new Line2D.Double( 1.0, 200000.0 ,0.0, 0.0).ptSegDist( 1.0, 199999.0 ) );
System.out.println( new Line2D.Double( 1.0, 2000000.0 ,0.0, 0.0).ptSegDist( 1.0, 1999999.0 ) );
System.out.println( new Line2D.Double( 1.0, 20000000.0,0.0, 0.0).ptSegDist( 1.0, 19999999.0 ) );
0.004999937545118085
5.000601076713239E-4
0.0
0.0
0.0
0.25
Это называется потеря точности при вычитании. Вот в этой строке (из JDK 1.6)
lenSq = px * px + py * py - projlenSq;
В машинной арифметике (а именно, IEEE 754 double) точно представимо лишь некоторое подмножество рациональных чисел. Поэтому, фактически, остается допускать, что любое число double находится в (V1 - e1, V1+e1).
Что происходит, когда вычитают два неточно заданных числа? Величины вычитаются, а погрешности складываются:
(V1 - V2 - (e1+e2) , V1 - V2 +(e1+e2))
В нашем случае серии из шести тестов V1-V2 убывает, а e1+e2 растет.
Кстати, если этот код откомпилировать GCC, то будет получен более осмысленный результат:
4.999938e-003
4.999999e-004
5.002929e-005
0.000000e+000
0.000000e+000
0.000000e+000
Неужли уже при тесте ( ( 0, 0 ) - ( 1, 20000 ) ) == ( 1, 19999 ) e1+e2 столь велико относительно v1 и v2?
Разница потому, что одинаковые конструкции языка высокого уровня по-разному транслируются в инструкции процессора, и разные компиляторы Си тоже дают разные результаты. Надо еще GCJ посмотреть, ради интереса.
Тип double -- можно сказать, что разный, т.к. настройки округления разные.
Хранить-то он позволяет, а вот при промежуточных вычислениях (если Вы не заметили, там и возведение в квадрат, и взятие квадратного корня) точность может теряться, в том числе и полностью (да, есть и термин такой: total loss of precision), поэтому проблемы должны быть и будут.
несколько вариантов (не применительно к олимпиадам, а в целом)
1. Использовать интервальный тип данных (к сожалению это невозможно в Java), что позволит определить погрешность выходных данных и сообщить, если ошибка слишком велика
2. Использовать более длинный тип данных, что позволит подсчитать верный результат
самый лучший способ:
3. Изменить формулу или алгоритм, чтобы потери точности при вычитании не было. (а также, по возможности и других источников накопления погрешности)
А какие вообще есть источники потери точности? Можно как-то быстро находить в исходнике проблемные места?
И ещё, давно интересует, как же всё-таки правильно выбирать погрешности при сравнении в задачах?
Если ты можешь переработать решение так, чтобы были только умножения, деления и сложения, точность возрастет драматически.
Хороший пример - задача G на NEERC 2007/2008 - там не проходило решение с вычитаниями.
А как ты выбираешь eps? Ставишь то, что упоминается в условии?
Помнится, около года назад на сборах была задача про каких-то выглядывающих кротов, которых нужно бить в соответствии с углами, так на разборе говорилось что-то о противности косинусов и том, что проходили [только] решения с 1e-12..1e-14.
И сейчас стараюсь поступать по возможности также.
Именно потому, что идиотизм с выбором eps я не понимаю. А случаи, когда задача сдается скажем только с eps=1e-6, и ни с каким другим, бывают (аналогично для других значений eps), и угадывать то того, как начать решать, что задумал автор, я не очень люблю :о)
А long double нас хотя бы частично не спасёт?)
У ptSegDistSq в отличие от ptLineDistSq, множество входных данных распадается на три области: в одной результат совпадает с ptLineDistSq, а в двух других искомое расстояние является расстоянием до одной из граничных точек отрезка. ptSegDistSq поэтому делает еще одно преобразование координат:
px = x2 - px;
py = y2 - py;
и дальше - в нашем примере - получаются малые числа, на которые точности хватает.
Если взять другой случай - просто удвоим длину отрезка, получим снова ноль
System.out.println( new Line2D.Double( 0.0, 0.0, 2.0, 400.0 ).ptSegDist( 1.0, 199.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 2.0, 4000.0 ).ptSegDist( 1.0, 1999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 2.0, 40000.0 ).ptSegDist( 1.0, 19999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 2.0, 400000.0 ).ptSegDist( 1.0, 199999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 2.0, 4000000.0 ).ptSegDist( 1.0, 1999999.0 ) );
System.out.println( new Line2D.Double( 0.0, 0.0, 2.0, 40000000.0).ptSegDist( 1.0, 19999999.0 ) );
this is the ptLineDist source code;
public static double
ptLineDistSq(double X1, double Y1,
double X2, double Y2,
double PX, double PY) {
X2 -= X1;
Y2 -= Y1;
PX -= X1;
PY -= Y1;
double dotprod = PX * X2 + PY * Y2;
double projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);double lenSq = PX * PX + PY * PY - projlenSq;if (lenSq < 0) {
lenSq = 0;
}
return lenSq;
}
public static doubleptLineDist(double X1, double Y1,double X2, double Y2,
double PX, double PY) {
return
return Math.sqrt(ptLineDistSq(X1, Y1, X2, Y2, PX, PY));
}
in the method
ptLineDistSqjava stander use dot-product to calculate the dist.and use dot*dot this maybe as larger as x^4,but
(X2 * X2 + Y2 * Y2) is x^2;so the result
projlenSqcould be make a flat error,and makelenSq could be very small,even to zero.
you can try write a new method use cross-product,then you will find it come up with the correct answer:
public static double pointToLineDist(Point p,Point A,Point B)
{
return Math.abs(p.sub(A).cross(B.sub(A))/B.sub(A).len());
}
this is the ptLineDist source code;
public static double
ptLineDistSq(double X1, double Y1,
double X2, double Y2,
double PX, double PY) {
X2 -= X1;
Y2 -= Y1;
PX -= X1;
PY -= Y1;
double dotprod = PX * X2 + PY * Y2;
double projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);double lenSq = PX * PX + PY * PY - projlenSq;if (lenSq < 0) {
lenSq = 0;
}
return lenSq;
}
public static doubleptLineDist(double X1, double Y1,double X2, double Y2,
double PX, double PY) {
return
return Math.sqrt(ptLineDistSq(X1, Y1, X2, Y2, PX, PY));
}
in the method
ptLineDistSqjava stander use dot-product to calculate the dist.and use dot*dot this maybe as larger as x^4,but
(X2 * X2 + Y2 * Y2) is x^2;so the result
projlenSqcould be make a flat error,and makelenSq could be very small,even to zero.
you can try write a new method use cross-product,then you will find it come up with the correct answer:
public static double pointToLineDist(Point p,Point A,Point B)
{
return Math.abs(p.sub(A).cross(B.sub(A))/B.sub(A).len());
}
this is the ptLineDist source code;
public static double
ptLineDistSq(double X1, double Y1,
double X2, double Y2,
double PX, double PY) {
X2 -= X1;
Y2 -= Y1;
PX -= X1;
PY -= Y1;
double dotprod = PX * X2 + PY * Y2;
double projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);double lenSq = PX * PX + PY * PY - projlenSq;if (lenSq < 0) {
lenSq = 0;
}
return lenSq;
}
public static doubleptLineDist(double X1, double Y1,double X2, double Y2,
double PX, double PY) {
return
return Math.sqrt(ptLineDistSq(X1, Y1, X2, Y2, PX, PY));
}
in the method
ptLineDistSqjava stander use dot-product to calculate the dist.and use dot*dot this maybe as larger as x^4,but
(X2 * X2 + Y2 * Y2) is x^2;so the result
projlenSqcould be make a flat error,and makelenSq could be very small,even to zero.
you can try write a new method use cross-product,then you will find it come up with the correct answer:
public static double pointToLineDist(Point p,Point A,Point B)
{
return Math.abs(p.sub(A).cross(B.sub(A))/B.sub(A).len());
}
this is the ptLineDist source code;
public static double
ptLineDistSq(double X1, double Y1,
double X2, double Y2,
double PX, double PY) {
X2 -= X1;
Y2 -= Y1;
PX -= X1;
PY -= Y1;
double dotprod = PX * X2 + PY * Y2;
double projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);double lenSq = PX * PX + PY * PY - projlenSq;if (lenSq < 0) {
lenSq = 0;
}
return lenSq;
}
public static doubleptLineDist(double X1, double Y1,double X2, double Y2,
double PX, double PY) {
return
return Math.sqrt(ptLineDistSq(X1, Y1, X2, Y2, PX, PY));
}
in the method
ptLineDistSqjava stander use dot-product to calculate the dist.and use dot*dot this maybe as larger as x^4,but
(X2 * X2 + Y2 * Y2) is x^2;so the result
projlenSqcould be make a flat error,and makelenSq could be very small,even to zero.
you can try write a new method use cross-product,then you will find it come up with the correct answer:
public static double pointToLineDist(Point p,Point A,Point B)
{
return Math.abs(p.sub(A).cross(B.sub(A))/B.sub(A).len());
}
this is the ptLineDist source code;
public static double
ptLineDistSq(double X1, double Y1,
double X2, double Y2,
double PX, double PY) {
X2 -= X1;
Y2 -= Y1;
PX -= X1;
PY -= Y1;
double dotprod = PX * X2 + PY * Y2;
double projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);double lenSq = PX * PX + PY * PY - projlenSq;if (lenSq < 0) {
lenSq = 0;
}
return lenSq;
}
public static doubleptLineDist(double X1, double Y1,double X2, double Y2,
double PX, double PY) {
return
return Math.sqrt(ptLineDistSq(X1, Y1, X2, Y2, PX, PY));
}
in the method
ptLineDistSqjava stander use dot-product to calculate the dist.and use dot*dot this maybe as larger as x^4,but
(X2 * X2 + Y2 * Y2) is x^2;so the result
projlenSqcould be make a flat error,and makelenSq could be very small,even to zero.
you can try write a new method use cross-product,then you will find it come up with the correct answer:
public static double pointToLineDist(Point p,Point A,Point B)
{
return Math.abs(p.sub(A).cross(B.sub(A))/B.sub(A).len());
}
this is the ptLineDist source code;
public static double
ptLineDistSq(double X1, double Y1,
double X2, double Y2,
double PX, double PY) {
X2 -= X1;
Y2 -= Y1;
PX -= X1;
PY -= Y1;
double dotprod = PX * X2 + PY * Y2;
double projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);double lenSq = PX * PX + PY * PY - projlenSq;if (lenSq < 0) {
lenSq = 0;
}
return lenSq;
}
public static doubleptLineDist(double X1, double Y1,double X2, double Y2,
double PX, double PY) {
return
return Math.sqrt(ptLineDistSq(X1, Y1, X2, Y2, PX, PY));
}
in the method
ptLineDistSqjava stander use dot-product to calculate the dist.and use dot*dot this maybe as larger as x^4,but
(X2 * X2 + Y2 * Y2) is x^2;so the result
projlenSqcould be make a flat error,and makelenSq could be very small,even to zero.
you can try write a new method use cross-product,then you will find it come up with the correct answer:
public static double pointToLineDist(Point p,Point A,Point B)
{
return Math.abs(p.sub(A).cross(B.sub(A))/B.sub(A).len());
}
this is the ptLineDist source code;
public static double
ptLineDistSq(double X1, double Y1,
double X2, double Y2,
double PX, double PY) {
X2 -= X1;
Y2 -= Y1;
PX -= X1;
PY -= Y1;
double dotprod = PX * X2 + PY * Y2;
double projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);double lenSq = PX * PX + PY * PY - projlenSq;if (lenSq < 0) {
lenSq = 0;
}
return lenSq;
}
public static doubleptLineDist(double X1, double Y1,double X2, double Y2,
double PX, double PY) {
return
return Math.sqrt(ptLineDistSq(X1, Y1, X2, Y2, PX, PY));
}
in the method
ptLineDistSqjava stander use dot-product to calculate the dist.and use dot*dot this maybe as larger as x^4,but
(X2 * X2 + Y2 * Y2) is x^2;so the result
projlenSqcould be make a flat error,and makelenSq could be very small,even to zero.
you can try write a new method use cross-product,then you will find it come up with the correct answer:
public static double pointToLineDist(Point p,Point A,Point B)
{
return Math.abs(p.sub(A).cross(B.sub(A))/B.sub(A).len());
}
Why there are so many reply by me.
P.S. wow,your photo is a cat.My ID is a cat too(cat=mao).
P. S. Are you on your avatar? :)
P.S. I'm not a girl.- -!
Well, you must have pressed the submit button several times, then.
May be I pressed but it didn't work,so I pressed several times.
- -!