Advertisement
marksman_

Untitled

Jan 14th, 2025
63
0
1 day
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.69 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. template<class Fun> class y_combinator_result {
  6.   Fun fun_;
  7. public:
  8.   template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
  9.   template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
  10. };
  11. template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
  12. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  13. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
  14. void debug_out() { cout << endl; }
  15. template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cout << ' ' << H; debug_out(T...); }
  16. #ifdef LOCAL_DEBUG
  17.   #define debug(...) cout << "[Line " <<  __LINE__ << "] (" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
  18. #else
  19.   #define debug(...)
  20. #endif
  21.  
  22. template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
  23. template<class T>
  24. struct Point {
  25.   typedef Point P;
  26.   T x, y;
  27.   explicit Point(T x=0, T y=0) : x(x), y(y) {}
  28.   bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
  29.   bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
  30.   P operator+(P p) const { return P(x+p.x, y+p.y); }
  31.   P operator-(P p) const { return P(x-p.x, y-p.y); }
  32.   P operator*(T d) const { return P(x*d, y*d); }
  33.   P operator/(T d) const { return P(x/d, y/d); }
  34.   T dot(P p) const { return x*p.x + y*p.y; }
  35.   T cross(P p) const { return x*p.y - y*p.x; }
  36.   T cross(P a, P b) const { return (a-*this).cross(b-*this); }
  37.   T dist2() const { return x*x + y*y; }
  38.   double dist() const { return sqrt((double)dist2()); }
  39.   // angle to x-axis in interval [-pi, pi]
  40.   double angle() const { return atan2(y, x); }
  41.   P unit() const { return *this/dist(); } // makes dist()=1
  42.   P perp() const { return P(-y, x); } // rotates +90 degrees
  43.   P normal() const { return perp().unit(); }
  44.   // returns point rotated 'a' radians ccw around the origin
  45.   P rotate(double a) const {
  46.     return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
  47.   friend ostream& operator<<(ostream& os, P p) {
  48.     return os << "(" << p.x << "," << p.y << ")"; }
  49. };
  50.  
  51. template<class P> bool onSegment(P s, P e, P p) {
  52.   return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
  53. }
  54.  
  55. template<class P> vector<P> segInter(P a, P b, P c, P d) {
  56.   auto oa = c.cross(d, a), ob = c.cross(d, b),
  57.        oc = a.cross(b, c), od = a.cross(b, d);
  58.   // Checks if intersection is single non-endpoint point.
  59.   if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) {
  60.     debug(oa, ob, oc, od);
  61.     return {(a * ob - b * oa) / (ob - oa)};
  62.   }
  63.   set<P> s;
  64.   if (onSegment(c, d, a)) s.insert(a);
  65.   if (onSegment(c, d, b)) s.insert(b);
  66.   if (onSegment(a, b, c)) s.insert(c);
  67.   if (onSegment(a, b, d)) s.insert(d);
  68.   return {s.begin(), s.end()};
  69. }
  70.  
  71. /*
  72.  
  73. 1
  74. -1000000000 1000000000 999999999 -1000000000 -999999999 999999999 0 0
  75.  
  76. AC: No
  77.  
  78. */
  79. void run_case() {
  80.   Point<int> a, b, c, d;
  81.   cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
  82.  
  83.   auto pts = segInter(a, b, c, d);
  84.   if (pts.empty()) {
  85.     cout << "NO\n";
  86.   } else {
  87.     cout << "YES\n";
  88.   }
  89. }
  90.  
  91. signed main() {
  92.   ios_base::sync_with_stdio(false);
  93.   cin.tie(nullptr);
  94.  
  95.   int T = 1;
  96.   // cin >> T;
  97.   for (int t = 1; t <= T; t++) {
  98.     // cout << "Case #" << t << ": ";
  99.     run_case();
  100.   }
  101.  
  102.   return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement