import java.util.Arrays;
import java.util.List;
class LineSegment {
public static class Point { public final double x;
public final double y;
public Point(double x,
double y
) { this.x = x;
this.y = y;
}
return "(" + x + "," + y + ")";
}
}
public static void main
(String[] args
) { LineSegment segment
= new LineSegment
(new Point(0,
3),
new Point(2,
0)); List<Point> pointList =
Point answer
= segment.
closestPoint(pointList
); System.
out.
println("The closest point is: " + answer
); }
private static double sqr(double x) {
return x * x;
}
private static double distanceSquared
(Point v,
Point w
) { return sqr(v.x - w.x) + sqr(v.y - w.y);
}
private final Point firstSegPoint
; private final Point secondSegPoint
; private final double segmentDistance;
private double xDifference;
private double yDifference;
public LineSegment
(Point firstSegPoint,
Point secondSegPoint
) { this.firstSegPoint = firstSegPoint;
this.secondSegPoint = secondSegPoint;
this.segmentDistance = distanceSquared(firstSegPoint, secondSegPoint);
this.xDifference = secondSegPoint.x - firstSegPoint.x;
this.yDifference = secondSegPoint.y - firstSegPoint.y;
}
public Point closestPoint
(List
<Point
> pointList
) { double minDistance
= Double.
POSITIVE_INFINITY;
for (Point point
: pointList
) { double distSquared = distToSegmentSquared(point);
if (distSquared < minDistance) {
answer = point;
minDistance = distSquared;
}
}
return answer;
}
private double distToSegmentSquared
(Point input
) { if (segmentDistance == 0)
return distanceSquared(input, firstSegPoint);
double xComponent = (input.x - firstSegPoint.x) * xDifference;
double yComponent = (input.y - firstSegPoint.y) * yDifference;
double t = (xComponent + yComponent) / segmentDistance;
if (closestPointIsFirst(t))
return distanceSquared(input, firstSegPoint);
if (closestPointIsSecond(t))
return distanceSquared(input, secondSegPoint);
Point closestPointOnLine
= new Point(firstSegPoint.
x + t
* xDifference, firstSegPoint.
y + t * yDifference);
return distanceSquared(input, closestPointOnLine);
}
private boolean closestPointIsFirst(double t) {
return t < 0;
}
private boolean closestPointIsSecond(double t) {
return t > 1;
}
}
CWltcG9ydCBqYXZhLnV0aWwuQXJyYXlzOwoJaW1wb3J0IGphdmEudXRpbC5MaXN0OwoJCgljbGFzcyBMaW5lU2VnbWVudCB7CgkJcHVibGljIHN0YXRpYyBjbGFzcyBQb2ludCB7CgkJCXB1YmxpYyBmaW5hbCBkb3VibGUgeDsKCQkJcHVibGljIGZpbmFsIGRvdWJsZSB5OwoJCgkJCXB1YmxpYyBQb2ludChkb3VibGUgeCwgZG91YmxlIHkpIHsKCQkJCXRoaXMueCA9IHg7CgkJCQl0aGlzLnkgPSB5OwoJCQl9CgkKCQkJcHVibGljIFN0cmluZyB0b1N0cmluZygpIHsKCQkJCXJldHVybiAiKCIgKyB4ICsgIiwiICsgeSArICIpIjsKCQkJfQoJCX0KCgkJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCQlMaW5lU2VnbWVudCBzZWdtZW50ID0gbmV3IExpbmVTZWdtZW50KG5ldyBQb2ludCgwLCAzKSwgbmV3IFBvaW50KDIsIDApKTsKCQkJTGlzdDxQb2ludD4gcG9pbnRMaXN0ID0KCQkJCQlBcnJheXMuYXNMaXN0KG5ldyBQb2ludFtdIHsgbmV3IFBvaW50KC01LCAzKSwgbmV3IFBvaW50KDEsIDEpLAoJCQkJCQkJbmV3IFBvaW50KDIsIDMpLCBuZXcgUG9pbnQoMCwgNSkgfSk7CgkKCQkJUG9pbnQgYW5zd2VyID0gc2VnbWVudC5jbG9zZXN0UG9pbnQocG9pbnRMaXN0KTsKCQkJU3lzdGVtLm91dC5wcmludGxuKCJUaGUgY2xvc2VzdCBwb2ludCBpczogIiArIGFuc3dlcik7CgkJfQoJCgkJcHJpdmF0ZSBzdGF0aWMgZG91YmxlIHNxcihkb3VibGUgeCkgewoJCQlyZXR1cm4geCAqIHg7CgkJfQoJCgkJcHJpdmF0ZSBzdGF0aWMgZG91YmxlIGRpc3RhbmNlU3F1YXJlZChQb2ludCB2LCBQb2ludCB3KSB7CgkJCXJldHVybiBzcXIodi54IC0gdy54KSArIHNxcih2LnkgLSB3LnkpOwoJCX0KCQoJCXByaXZhdGUgZmluYWwgUG9pbnQgZmlyc3RTZWdQb2ludDsKCQlwcml2YXRlIGZpbmFsIFBvaW50IHNlY29uZFNlZ1BvaW50OwoJCXByaXZhdGUgZmluYWwgZG91YmxlIHNlZ21lbnREaXN0YW5jZTsKCQlwcml2YXRlIGRvdWJsZSB4RGlmZmVyZW5jZTsKCQlwcml2YXRlIGRvdWJsZSB5RGlmZmVyZW5jZTsKCQoJCXB1YmxpYyBMaW5lU2VnbWVudChQb2ludCBmaXJzdFNlZ1BvaW50LCBQb2ludCBzZWNvbmRTZWdQb2ludCkgewoJCQl0aGlzLmZpcnN0U2VnUG9pbnQgPSBmaXJzdFNlZ1BvaW50OwoJCQl0aGlzLnNlY29uZFNlZ1BvaW50ID0gc2Vjb25kU2VnUG9pbnQ7CgkJCXRoaXMuc2VnbWVudERpc3RhbmNlID0gZGlzdGFuY2VTcXVhcmVkKGZpcnN0U2VnUG9pbnQsIHNlY29uZFNlZ1BvaW50KTsKCQkJdGhpcy54RGlmZmVyZW5jZSA9IHNlY29uZFNlZ1BvaW50LnggLSBmaXJzdFNlZ1BvaW50Lng7CgkJCXRoaXMueURpZmZlcmVuY2UgPSBzZWNvbmRTZWdQb2ludC55IC0gZmlyc3RTZWdQb2ludC55OwoJCX0KCQoJCXB1YmxpYyBQb2ludCBjbG9zZXN0UG9pbnQoTGlzdDxQb2ludD4gcG9pbnRMaXN0KSB7CgkJCWRvdWJsZSBtaW5EaXN0YW5jZSA9IERvdWJsZS5QT1NJVElWRV9JTkZJTklUWTsKCQkJUG9pbnQgYW5zd2VyID0gbnVsbDsKCQoJCQlmb3IgKFBvaW50IHBvaW50IDogcG9pbnRMaXN0KSB7CgkJCQlkb3VibGUgZGlzdFNxdWFyZWQgPSBkaXN0VG9TZWdtZW50U3F1YXJlZChwb2ludCk7CgkJCQlpZiAoZGlzdFNxdWFyZWQgPCBtaW5EaXN0YW5jZSkgewoJCQkJCWFuc3dlciA9IHBvaW50OwoJCQkJCW1pbkRpc3RhbmNlID0gZGlzdFNxdWFyZWQ7CgkJCQl9CgkJCX0KCQoJCQlyZXR1cm4gYW5zd2VyOwoJCX0KCQoJCXByaXZhdGUgZG91YmxlIGRpc3RUb1NlZ21lbnRTcXVhcmVkKFBvaW50IGlucHV0KSB7CgkJCWlmIChzZWdtZW50RGlzdGFuY2UgPT0gMCkKCQkJCXJldHVybiBkaXN0YW5jZVNxdWFyZWQoaW5wdXQsIGZpcnN0U2VnUG9pbnQpOwoJCgkJCWRvdWJsZSB4Q29tcG9uZW50ID0gKGlucHV0LnggLSBmaXJzdFNlZ1BvaW50LngpICogeERpZmZlcmVuY2U7CgkJCWRvdWJsZSB5Q29tcG9uZW50ID0gKGlucHV0LnkgLSBmaXJzdFNlZ1BvaW50LnkpICogeURpZmZlcmVuY2U7CgkJCWRvdWJsZSB0ID0gKHhDb21wb25lbnQgKyB5Q29tcG9uZW50KSAvIHNlZ21lbnREaXN0YW5jZTsKCQkJaWYgKGNsb3Nlc3RQb2ludElzRmlyc3QodCkpCgkJCQlyZXR1cm4gZGlzdGFuY2VTcXVhcmVkKGlucHV0LCBmaXJzdFNlZ1BvaW50KTsKCQkJaWYgKGNsb3Nlc3RQb2ludElzU2Vjb25kKHQpKQoJCQkJcmV0dXJuIGRpc3RhbmNlU3F1YXJlZChpbnB1dCwgc2Vjb25kU2VnUG9pbnQpOwoJCQlQb2ludCBjbG9zZXN0UG9pbnRPbkxpbmUgPQoJCQkJCW5ldyBQb2ludChmaXJzdFNlZ1BvaW50LnggKyB0ICogeERpZmZlcmVuY2UsIGZpcnN0U2VnUG9pbnQueQoJCQkJCQkJKyB0ICogeURpZmZlcmVuY2UpOwoJCQlyZXR1cm4gZGlzdGFuY2VTcXVhcmVkKGlucHV0LCBjbG9zZXN0UG9pbnRPbkxpbmUpOwoJCX0KCQoJCXByaXZhdGUgYm9vbGVhbiBjbG9zZXN0UG9pbnRJc0ZpcnN0KGRvdWJsZSB0KSB7CgkJCXJldHVybiB0IDwgMDsKCQl9CgkKCQlwcml2YXRlIGJvb2xlYW4gY2xvc2VzdFBvaW50SXNTZWNvbmQoZG91YmxlIHQpIHsKCQkJcmV0dXJuIHQgPiAxOwoJCX0KCX0KCg==