Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- template<class Fun> class y_combinator_result {
- Fun fun_;
- public:
- template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
- template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
- };
- template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
- template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
- 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 << '}'; }
- void debug_out() { cout << endl; }
- template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cout << ' ' << H; debug_out(T...); }
- #ifdef LOCAL_DEBUG
- #define debug(...) cout << "[Line " << __LINE__ << "] (" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
- #else
- #define debug(...)
- #endif
- template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
- template<class T>
- struct Point {
- typedef Point P;
- T x, y;
- explicit Point(T x=0, T y=0) : x(x), y(y) {}
- bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
- bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
- P operator+(P p) const { return P(x+p.x, y+p.y); }
- P operator-(P p) const { return P(x-p.x, y-p.y); }
- P operator*(T d) const { return P(x*d, y*d); }
- P operator/(T d) const { return P(x/d, y/d); }
- T dot(P p) const { return x*p.x + y*p.y; }
- T cross(P p) const { return x*p.y - y*p.x; }
- T cross(P a, P b) const { return (a-*this).cross(b-*this); }
- T dist2() const { return x*x + y*y; }
- double dist() const { return sqrt((double)dist2()); }
- // angle to x-axis in interval [-pi, pi]
- double angle() const { return atan2(y, x); }
- P unit() const { return *this/dist(); } // makes dist()=1
- P perp() const { return P(-y, x); } // rotates +90 degrees
- P normal() const { return perp().unit(); }
- // returns point rotated 'a' radians ccw around the origin
- P rotate(double a) const {
- return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
- friend ostream& operator<<(ostream& os, P p) {
- return os << "(" << p.x << "," << p.y << ")"; }
- };
- template<class P> bool onSegment(P s, P e, P p) {
- return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
- }
- template<class P> vector<P> segInter(P a, P b, P c, P d) {
- auto oa = c.cross(d, a), ob = c.cross(d, b),
- oc = a.cross(b, c), od = a.cross(b, d);
- // Checks if intersection is single non-endpoint point.
- if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) {
- debug(oa, ob, oc, od);
- return {(a * ob - b * oa) / (ob - oa)};
- }
- set<P> s;
- if (onSegment(c, d, a)) s.insert(a);
- if (onSegment(c, d, b)) s.insert(b);
- if (onSegment(a, b, c)) s.insert(c);
- if (onSegment(a, b, d)) s.insert(d);
- return {s.begin(), s.end()};
- }
- /*
- 1
- -1000000000 1000000000 999999999 -1000000000 -999999999 999999999 0 0
- AC: No
- */
- void run_case() {
- Point<int> a, b, c, d;
- cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
- auto pts = segInter(a, b, c, d);
- if (pts.empty()) {
- cout << "NO\n";
- } else {
- cout << "YES\n";
- }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int T = 1;
- // cin >> T;
- for (int t = 1; t <= T; t++) {
- // cout << "Case #" << t << ": ";
- run_case();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement