This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#define PROBLEM \ "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_2_C" #define ERROR 0.00000001 #include <algorithm> #include <iomanip> #include <iostream> #include <vector> #include "geometry/line.hpp" #include "geometry/point.hpp" namespace ebi { void main_() { int q; std::cin >> q; while (q--) { point p0, p1, p2, p3; std::cin >> p0.x >> p0.y >> p1.x >> p1.y; std::cin >> p2.x >> p2.y >> p3.x >> p3.y; point cross = cross_point(p0, p1, p2, p3); std::cout << cross.x << " " << cross.y << '\n'; } } } // namespace ebi int main() { std::cout << std::fixed << std::setprecision(15); std::cin.tie(nullptr); std::ios::sync_with_stdio(false); ebi::main_(); }
#line 1 "test/geometry/cross_point.test.cpp" #define PROBLEM \ "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_2_C" #define ERROR 0.00000001 #include <algorithm> #include <iomanip> #include <iostream> #include <vector> #line 2 "geometry/line.hpp" #include <cassert> #include <cmath> #line 2 "geometry/point.hpp" #line 6 "geometry/point.hpp" #include <cstdint> #line 9 "geometry/point.hpp" namespace ebi { constexpr long double EPS = 1e-10; const long double PI = std::acos(-1); namespace internal { int sgn(long double a) { return (a < -EPS) ? -1 : (a > EPS) ? 1 : 0; } long double add(long double a, long double b) { if (std::abs(a + b) < EPS * (std::abs(a) + std::abs(b))) return 0; return a + b; } } // namespace internal long double arg_to_radian(long double arg) { return PI * arg / (long double)(180); } struct point { long double x, y; point() = default; point(long double x, long double y) : x(x), y(y) {} point &operator+=(const point rhs) noexcept { x = internal::add(x, rhs.x); y = internal::add(y, rhs.y); return *this; } point &operator-=(const point rhs) noexcept { x = internal::add(x, -rhs.x); y = internal::add(y, -rhs.y); return *this; } point &operator*=(const point rhs) noexcept { long double _x = internal::add(x * rhs.x, -y * rhs.y); long double _y = internal::add(x * rhs.y, y * rhs.x); x = _x; y = _y; return *this; } point &operator*=(const long double k) noexcept { x *= k; y *= k; return *this; } point &operator/=(const long double k) { assert(internal::sgn(k) != 0); x /= k; y /= k; return *this; } point operator+(const point &rhs) const noexcept { return point(*this) += rhs; } point operator-(const point &rhs) const noexcept { return point(*this) -= rhs; } point operator*(const point &rhs) const noexcept { return point(*this) *= rhs; } point operator*(const long double rhs) const noexcept { return point(*this) *= rhs; } point operator/(const long double rhs) const { return point(*this) /= rhs; } point operator-() const noexcept { return point(0, 0) - *this; } long double abs() const noexcept { return std::sqrt(internal::add(x * x, y * y)); } long double dot(const point rhs) const noexcept { return internal::add(x * rhs.x, y * rhs.y); } long double det(const point rhs) const noexcept { return internal::add(x * rhs.y, -y * rhs.x); } // arctan(y/x) (単位はラジアン) long double arg() const { return std::atan2(y, x); } // x昇順, その後y昇順 bool operator<(const point &rhs) const noexcept { if (internal::sgn(x - rhs.x)) return internal::sgn(x - rhs.x) < 0; return internal::sgn(y - rhs.y) < 0; } bool operator==(const point &rhs) const noexcept { if (internal::sgn(x - rhs.x) == 0 && internal::sgn(y - rhs.y) == 0) return true; else return false; } bool operator!=(const point &rhs) const noexcept { return !((*this) == rhs); } }; std::ostream &operator<<(std::ostream &os, const point &a) { return os << a.x << " " << a.y; } std::istream &operator>>(std::istream &os, point &a) { return os >> a.x >> a.y; } point conj(const point &a) { return point(a.x, -a.y); } // 点a をang(ラジアン)回転する point rot(const point &a, long double ang) { return point(std::cos(ang) * a.x - std::sin(ang) * a.y, std::sin(ang) * a.x + std::cos(ang) * a.y); } point rot90(const point &a) { return point(-a.y, a.x); } long double dot(const point &a, const point &b) { return a.dot(b); } long double det(const point &a, const point &b) { return a.det(b); } long double abs(const point &a) { return a.abs(); } long double norm(const point &a) { return internal::add(a.x * a.x, a.y * a.y); } int isp(const point &a, const point &b, const point &c) { int flag = internal::sgn(det(b - a, c - a)); if (flag == 0) { if (internal::sgn(dot(b - a, c - a)) < 0) return -2; if (internal::sgn(dot(a - b, c - b)) < 0) return +2; } return flag; } // 分割統治で最近点対を求める O(N log N) long double closest_pair(std::vector<point> p) { std::sort(p.begin(), p.end()); int n = p.size(); auto f = [&](auto &&self, int l, int r) -> long double { if (r - l == 1) { return 1e9; } int mid = (l + r) / 2; long double x = p[mid].x; long double d = std::min(self(self, l, mid), self(self, mid, r)); std::vector<point> b; b.reserve(r - l); int j = mid; for (int i = l; i < mid; i++) { while (j < r && p[j].y <= p[i].y) { b.emplace_back(p[j++]); } b.emplace_back(p[i]); } while (j < r) { b.emplace_back(p[j++]); } for (int i = 0; i < r - l; i++) { p[l + i] = b[i]; } b.clear(); for (int i = l; i < r; i++) { if (std::abs(p[i].x - x) >= d) continue; for (int j = int(b.size()) - 1; j >= 0; j--) { if (p[i].y - b[j].y >= d) break; d = std::min(d, abs(p[i] - b[j])); } b.emplace_back(p[i]); } return d; }; return f(f, 0, n); } // ∠ABCを求める(ラジアン) long double angle(const point &A, const point &B, const point &C) { long double a = (B - C).abs(), b = (C - A).abs(), c = (A - B).abs(); long double cos = internal::add(internal::add(a * a, c * c), -b * b) / (2.0 * c * a); return std::acos(cos); } // 符号付き long double calc_ang(point a, point b, point c) { long double cos = dot((a - b), (c - b)) / (abs(a - b) * abs(c - b)); long double sin = det((a - b), (c - b)) / (abs(a - b) * abs(c - b)); return std::atan2(sin, cos); } void arg_sort(std::vector<point> &a) { int n = a.size(); std::vector ps(4, std::vector<point>()); auto idx = [](point v) -> int { if (v.y >= 0) return (v.x >= 0) ? 0 : 1; else return (v.x >= 0) ? 3 : 2; }; for (auto p : a) { assert(!(p.x == 0 && p.y == 0)); ps[idx(p)].emplace_back(p); } a.clear(); a.reserve(n); for (int i = 0; i < 4; i++) { std::sort(ps[i].begin(), ps[i].end(), [](point &p1, point &p2) -> bool { int flag = internal::sgn(internal::add(p1.x * p2.y, -p2.x * p1.y)); return flag == 0 ? (norm(p1) < norm(p2)) : flag > 0; }); for (auto &p : ps[i]) a.emplace_back(p); } return; } template <class T> void arg_sort_ll(std::vector<std::pair<T, T>> &a) { using Point = std::pair<T, T>; int n = a.size(); std::vector ps(4, std::vector<Point>()); auto idx = [](Point v) -> int { if (v.second >= 0) return (v.first >= 0) ? 0 : 1; else return (v.first >= 0) ? 3 : 2; }; for (auto p : a) { assert(!(p.first == 0 && p.second == 0)); ps[idx(p)].emplace_back(p); } a.clear(); a.reserve(n); for (int i = 0; i < 4; i++) { std::sort(ps[i].begin(), ps[i].end(), [](Point &p1, Point &p2) -> bool { T flag = p1.first * p2.second - p2.first * p1.second; return flag == 0 ? (p1.first * p1.first + p1.second * p1.second < p2.first * p2.first + p2.second * p2.second) : flag > 0; }); for (auto &p : ps[i]) a.emplace_back(p); } return; } } // namespace ebi #line 7 "geometry/line.hpp" namespace ebi { struct line { point a, b; line(long double x1, long double y1, long double x2, long double y2) : a(x1, y1), b(x2, y2) {} line(const point &a, const point &b) : a(a), b(b) {} point proj(const point &p) const { return a + (b - a) * (dot(b - a, p - a) / norm(b - a)); } point relf(const point &p) const { return proj(p) * double(2) - p; } long double distance(const point &c) const { return std::abs(det(c - a, b - a) / abs(b - a)); } }; int intersection(const line &a, const line &b) { if (internal::sgn(det(a.b - a.a, b.a - b.b)) != 0) { if (internal::sgn(dot(a.b - a.a, b.b - b.a)) == 0) { // 垂直 return 1; } return 0; // 交差 } else if (internal::sgn(det(a.b - a.a, b.a - a.a)) != 0) { // 平行 return 2; } else { // 同一直線 return 3; } } point cross_point(const point &a, const point &b, const point &c, const point &d) { return a + (b - a) * det(c - a, d - c) / det(b - a, d - c); } // 交点があるか確認する! point cross_point(const line &s, const line &t) { assert(intersection(s, t) < 2); return s.a + (s.b - s.a) * det(t.a - s.a, t.b - t.a) / det(s.b - s.a, t.b - t.a); } // 直線aと点cの距離 long double distance(const line &a, const point &c) { return std::abs(det(c - a.a, a.b - a.a) / abs(a.b - a.a)); } long double distance(const line &a, const line &b) { if (intersection(a, b) < 2) { return 0; } else { return distance(a, b.a); } } } // namespace ebi #line 12 "test/geometry/cross_point.test.cpp" namespace ebi { void main_() { int q; std::cin >> q; while (q--) { point p0, p1, p2, p3; std::cin >> p0.x >> p0.y >> p1.x >> p1.y; std::cin >> p2.x >> p2.y >> p3.x >> p3.y; point cross = cross_point(p0, p1, p2, p3); std::cout << cross.x << " " << cross.y << '\n'; } } } // namespace ebi int main() { std::cout << std::fixed << std::setprecision(15); std::cin.tie(nullptr); std::ios::sync_with_stdio(false); ebi::main_(); }