fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) begin(x), end(x)
  4. typedef long long ll;
  5. using namespace std;
  6.  
  7. const double EPS = 1e-8;
  8. template <typename T> int sgn(T x) { return x < -EPS ? -1 : x > EPS; }
  9. template <class T> struct Point {
  10.     typedef Point P;
  11.     T x, y;
  12.     explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
  13.     bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
  14.     bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
  15.     P operator+(P p) const { return P(x + p.x, y + p.y); }
  16.     P operator-(P p) const { return P(x - p.x, y - p.y); }
  17.     P operator*(T d) const { return P(x * d, y * d); }
  18.     P operator/(T d) const { return P(x / d, y / d); }
  19.     T dot(P p) const { return x * p.x + y * p.y; }
  20.     T cross(P p) const { return x * p.y - y * p.x; }
  21.     T cross(P a, P b) const { return (a - *this).cross(b - *this); }
  22.     T dist2() const { return x * x + y * y; }
  23.     double dist() const { return sqrt((double)dist2()); }
  24.     // angle to x-axis in interval [-pi, pi]
  25.     double angle() const { return atan2(y, x); }
  26.     P unit() const { return *this / dist(); } // makes dist()=1
  27.     P perp() const { return P(-y, x); }       // rotates +90 degrees
  28.     P normal() const { return perp().unit(); }
  29.     // returns point rotated 'a' radians ccw around the origin
  30.     P rotate(double a) const { return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
  31. };
  32.  
  33. template <class P> bool onSegment(P s, P e, P p) { return sgn(s.cross(e, p)) == 0 && sgn((s - p).dot(e - p)) <= 0; }
  34. template <class P> bool segInterProper(P a, P b, P c, P d, P &out) {
  35.     double oa = c.cross(d, a), ob = c.cross(d, b), oc = a.cross(b, c), od = a.cross(b, d);
  36.     if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) {
  37.         out = (a * ob - b * oa) / (ob - oa);
  38.         return true;
  39.     }
  40.     return false;
  41. }
  42. template <class P> set<P> segInter(P a, P b, P c, P d) {
  43.     P out;
  44.     if (segInterProper(a, b, c, d, out))
  45.         return {out};
  46.     set<P> s;
  47.     if (onSegment(c, d, a))
  48.         s.insert(a);
  49.     if (onSegment(c, d, b))
  50.         s.insert(b);
  51.     if (onSegment(a, b, c))
  52.         s.insert(c);
  53.     if (onSegment(a, b, d))
  54.         s.insert(d);
  55.     return s;
  56. }
  57. typedef Point<double> P;
  58. ostream &operator<<(ostream &os, P p) { return cout << p.x + EPS << " " << p.y + EPS; }
  59. istream &operator>>(istream &is, P p) { return cin >> p.x >> p.y; }
  60. signed main() {
  61.     ios::sync_with_stdio(0);
  62.     cin.tie(0);
  63.     int N;
  64.     cin >> N;
  65.     cout << fixed << setprecision(2);
  66.     for (int i = 0; i < N; i++) {
  67.         P a, b, c, d;
  68.         cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
  69.         auto res = segInter(a, b, c, d);
  70.         if (res.size() == 0) {
  71.             cout << "none" << endl;
  72.         } else if (res.size() == 1) {
  73.             cout << *res.begin() << endl;
  74.         } else {
  75.             vector<P> t(res.begin(), res.end());
  76.             cout << t[0] << ' ' << t[1] << endl;
  77.         }
  78.     }
  79. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
5
-10 0 10 0 0 -10 0 10
-10 0 10 0 -5 0 5 0
1 1 1 1 1 1 2 1
1 1 1 1 2 1 2 1
1871 5789 216 -517 189 -518 3851 1895
stdout 
0.00 0.00
-5.00 0.00 5.00 0.00
1.00 1.00
none
221.33 -496.70
https://ideone.com/xT9jXo
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!