I am solving the task about finding pairwise distance between these objects: point, segment, ray and line (it is not from USACO Guide). And I got stuck: WA on 107-th test. Here is my code:
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr long double eps = 1E-9;
template<class T>
struct Point {
T x, y;
Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {}
template<class U>
operator Point<U>() {
return Point<U>(U(x), U(y));
}
Point& operator+=(Point p)& {
x += p.x;
y += p.y;
return *this;
}
Point& operator-=(Point p)& {
x -= p.x;
y -= p.y;
return *this;
}
Point& operator*=(T v)& {
x *= v;
y *= v;
return *this;
}
Point operator-() const {
return Point(-x, -y);
}
friend Point operator+(Point a, Point b) {
return a += b;
}
friend Point operator-(Point a, Point b) {
return a -= b;
}
friend Point operator*(Point a, T b) {
return a *= b;
}
friend Point operator*(T a, Point b) {
return b *= a;
}
friend bool operator==(Point a, Point b) {
return abs(a.x - b.x) < eps && abs(a.y - b.y) < eps;
}
friend bool operator!=(Point a, Point b) {
return !(a == b);
}
friend istream& operator>>(istream& is, Point& p) {
return is >> p.x >> p.y;
}
friend ostream& operator<<(ostream& os, Point p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
using V = long double;
using P = Point<V>;
template<class T>
T dot(Point<T> a, Point<T> b) {
return a.x * b.x + a.y * b.y;
}
template<class T>
T cross(Point<T> a, Point<T> b) {
return a.x * b.y - a.y * b.x;
}
template<class T>
T square(Point<T> p) {
return dot(p, p);
}
template<class T>
double length(Point<T> p) {
return sqrt(double(square(p)));
}
long double length(Point<long double> p) {
return sqrt(square(p));
}
template<class T>
struct Line {
Point<T> a, b;
T A, B, C;
Line(Point<T> a_ = Point<T>(), Point<T> b_ = Point<T>()) : a(a_), b(b_), A(-(b_ - a_).y), B((b_ - a_).x), C(-dot(Point<T>(A, B), a_)) {}
T func(Point<T> p) {
return A * p.x + B * p.y + C;
}
long double dist(Point<T> p) {
return abs(func(p)) / length(Point(A, B));
}
void scale(long double len) {
a = P(a);
b = P(b);
b = a + len / length(b - a) * (b - a);
}
};
using L = Line<V>;
template<class T>
bool SegmentIntersection(Line<T> l1, Line<T> l2) {
if (std::max(l1.a.x, l1.b.x) + eps < std::min(l2.a.x, l2.b.x)) {
return false;
}
if (std::max(l2.a.x, l2.b.x) + eps < std::min(l1.a.x, l1.b.x)) {
return false;
}
if (std::max(l1.a.y, l1.b.y) + eps < std::min(l2.a.y, l2.b.y)) {
return false;
}
if (std::max(l2.a.y, l2.b.y) + eps < std::min(l1.a.y, l1.b.y)) {
return false;
}
auto cp1 = cross(l1.b - l1.a, l2.a - l1.a);
auto cp2 = cross(l1.b - l1.a, l2.b - l1.a);
auto cp3 = cross(l2.b - l2.a, l1.a - l2.a);
auto cp4 = cross(l2.b - l2.a, l1.b - l2.a);
if ((cp1 > eps && cp2 > eps) || (cp1 < -eps && cp2 < -eps) || (cp3 > eps && cp4 > eps) || (cp3 < -eps && cp4 < -eps)) {
return false;
}
return true;
}
template<class T>
long double PtoP(Point<T> a, Point<T> b) {
return length(a - b);
}
template<class T>
long double PtoS(Point<T> a, Line<T> l) {
if (dot(l.b - l.a, a - l.a) < -eps) {
return PtoP(l.a, a);
}
if (dot(l.a - l.b, a - l.b) < -eps) {
return PtoP(l.b, a);
}
return l.dist(a);
}
template<class T>
long double PtoR(Point<T> a, Line<T> l) {
if (dot(l.b - l.a, a - l.a) < -eps) {
return PtoP(l.a, a);
}
return l.dist(a);
}
template<class T>
long double PtoL(Point<T> a, Line<T> l) {
return l.dist(a);
}
template<class T>
long double StoS(Line<T> l1, Line<T> l2) {
if (SegmentIntersection(l1, l2)) {
return 0;
}
long double ans = 1E18;
for (auto p : { l1.a, l1.b }) {
ans = std::min(ans, PtoS(p, l2));
}
for (auto p : { l2.a, l2.b }) {
ans = std::min(ans, PtoS(p, l1));
}
return ans;
}
template<class T>
long double StoR(Line<T> l1, Line<T> l2) {
l2.scale(2E9);
return StoS(l1, l2);
}
template<class T>
long double StoL(Line<T> l1, Line<T> l2) {
l2.scale(1E9);
swap(l2.a, l2.b);
l2.scale(2E9);
return StoS(l1, l2);
}
template<class T>
long double RtoR(Line<T> l1, Line<T> l2) {
if (cross(l1.b - l1.a, l2.b - l2.a) == 0) {
return std::min(PtoR(l1.a, l2), PtoR(l2.a, l1));
}
l1.scale(2E9);
l2.scale(2E9);
return StoS(l1, l2);
}
template<class T>
long double RtoL(Line<T> l1, Line<T> l2) {
if (cross(l1.b - l1.a, l2.b - l2.a) == 0) {
return l2.dist(l1.a);
}
l1.scale(2E9);
l2.scale(1E9);
swap(l2.a, l2.b);
l2.scale(2E9);
return StoS(l1, l2);
}
template<class T>
long double LtoL(Line<T> l1, Line<T> l2) {
if (cross(l1.b - l1.a, l2.b - l2.a) == 0) {
return l2.dist(l1.a);
}
return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
Point<i64> A, B, C, D;
cin >> A >> B >> C >> D;
cout << PtoP(A, C) << '\n';
cout << PtoS(A, Line(C, D)) << '\n';
cout << PtoR(A, Line(C, D)) << '\n';
cout << PtoL(A, Line(C, D)) << '\n';
cout << PtoS(C, Line(A, B)) << '\n';
cout << StoS(Line(A, B), Line(C, D)) << '\n';
cout << StoR(Line(A, B), Line(C, D)) << '\n';
cout << StoL(Line(A, B), Line(C, D)) << '\n';
cout << PtoR(C, Line(A, B)) << '\n';
cout << StoR(Line(C, D), Line(A, B)) << '\n';
cout << RtoR(Line(A, B), Line(C, D)) << '\n';
cout << RtoL(Line(A, B), Line(C, D)) << '\n';
cout << PtoL(C, Line(A, B)) << '\n';
cout << StoL(Line(C, D), Line(A, B)) << '\n';
cout << RtoL(Line(C, D), Line(A, B)) << '\n';
cout << LtoL(Line(A, B), Line(C, D)) << '\n';
}
I interpreted lines and rays as segments using bounding box because given coordinates lie in the range [-10000; 10000]. I appreciate any help!