Line Segment Intersection

#include <iostream>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;

constexpr double PI = 3.14159265358979323846;

template<class T>
struct Vec {
  T x, y;
  Vec() : x(0), y(0) {}
  Vec(T x, T y) : x(x), y(y) {}
  Vec operator+(Vec o) const { return Vec(x+o.x,y+o.y); }
  Vec operator-(Vec o) const { return Vec(x-o.x,y-o.y); }
  Vec operator*(Vec o) const { return Vec(x*o.x,y*o.y); }
  Vec operator/(Vec o) const { return Vec(x/o.x,y/o.y); }
  Vec operator+(T o) const { return Vec(x+o,y+o); }
  Vec operator-(T o) const { return Vec(x-o,y-o); }
  Vec operator*(T o) const { return Vec(x*o,y*o); }
  Vec operator/(T o) const { return Vec(x/o,y/o); }
  Vec operator-() const { return Vec(-x,-y); }
  explicit operator bool() const { return x||y; }
  bool operator==(Vec o) const { return x==o.x&&y==o.y; }
  bool operator!=(Vec o) const { return x!=o.x||y!=o.y; }
  bool operator<(Vec o) const { return x<o.x||(x==o.x&&y<o.y); }
  bool operator>(Vec o) const { return o<*this; }
  bool operator<=(Vec o) const { return x<o.x||(x==o.x&&y<=o.y); }
  bool operator>=(Vec o) const { return o<=*this; }
  void operator+=(Vec o) { x+=o.x;y+=o.y; }
  void operator-=(Vec o) { x-=o.x;y-=o.y; }
  void operator*=(Vec o) { x*=o.x;y*=o.y; }
  void operator/=(Vec o) { x/=o.x;y/=o.y; }
  void operator+=(T o) { x+=o;y+=o; }
  void operator-=(T o) { x-=o;y-=o; }
  void operator*=(T o) { x*=o;y*=o; }
  void operator/=(T o) { x/=o;y/=o; }
  T dot(Vec o) const { return x*o.x + y*o.y; }
  /** left > 0, right < 0, same/opposite = 0 */
  T cross(Vec o) const { return x*o.y - y*o.x; }
  /** more left = bigger */
  T rightturn(Vec o) const {
    T d = dot(o), c = cross(o);
    return d < 0 ? copysign(d-1,c) : c;
  }
  T len2() const { return x*x + y*y; };
  T len() const { return sqrt(x*x + y*y); };
  Vec norm() const { return *this * (1 / len()); }
  /** 90deg counterclockwise/left */
  Vec perp() const { Vec(-y, x); }
  /** counterclockwise/left in radians */
  Vec rot(T a) const { const T sa = sin(a), ca = cos(a); return Vec(x*ca - y*sa, x*sa + y*ca); }
  friend istream& operator>>(istream& is, Vec& o) { return cin >> o.x >> o.y; }
  friend ostream& operator<<(ostream& os, Vec o) { return cout << '(' << o.x << ',' << o.y << ')'; }
};
using pd = Vec<double>;

double polygonArea(const vector<pd>& p) {
  assert(sz(p) >= 3);
  double sum = p.back().cross(p.front());
  rep(i,1,sz(p)) {
    sum += p[i-1].cross(p[i]);
  }
  return abs(sum)/2;
}

bool pointIntersect(pd p1, pd p2, pd p3, pd p4) {
  if (p2<p1) swap(p1,p2);
  if (p4<p3) swap(p3,p4);
  double c1 = (p1-p3).cross(p2-p3);
  double c2 = (p1-p4).cross(p2-p4);
  double c3 = (p3-p1).cross(p4-p1);
  double c4 = (p3-p2).cross(p4-p2);
  if (c1 == 0) return p1<=p3 && p3<=p2;
  if (c2 == 0) return p1<=p4 && p4<=p2;
  if (c3 == 0) return p3<=p1 && p1<=p4;
  if (c4 == 0) return p3<=p2 && p2<=p4;
  return (c1<0) != (c2<0) && (c3<0) != (c4<0);
}

int main() {
  int n;
  cin >> n;
  rep(i,0,n) {
    pd p1, p2, p3, p4;
    cin >> p1 >> p2 >> p3 >> p4;
    cout << (pointIntersect(p1,p2,p3,p4) ? "YES\n" : "NO\n");
  }
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED