#include <bits/stdc++.h>
using namespace std;
using namespace rel_ops;
extern const double nil;
const double eps = 1e-8;
const double pi = 3.1415926535897932384626;
const double na = sqrt(-1);
const double inf = 1.0 / nil;
const double nil = 0.0;
inline bool lt(double a, double b) { return b - a >= eps; }
inline bool gt(double a, double b) { return a - b >= eps; }
inline bool le(double a, double b) { return a - b < eps; }
inline bool ge(double a, double b) { return b - a < eps; }
inline bool eq(double a, double b) { return le(a, b) && ge(a, b); }
inline bool ne(double a, double b) { return lt(a, b) || gt(a, b); }
class Vect {
 public:
  double x, y;
  Vect() : x(0), y(0) {}
  Vect(double x, double y) : x(x), y(y) {}
  operator bool() const { return x == x && y == y; }
  bool operator==(const Vect& r) const { return eq(x, r.x) && eq(y, r.y); }
  bool operator<(const Vect& r) const {
    return lt(x, r.x) || (eq(x, r.x) && lt(y, r.y));
  }
  double len() const { return sqrt(x * x + y * y); }
  double dir() const { return atan2(y, x); }
  double operator*(const Vect& r) const { return x * r.y - y * r.x; }
  double operator%(const Vect& r) const { return x * r.x + y * r.y; }
  const Vect operator-() const { return Vect(-x, -y); }
  const Vect operator~() const { return *this / len(); }
  const Vect ort() const { return Vect(-y, x); }
  const Vect rot(double a) const {
    return Vect(cos(a) * x - sin(a) * y, sin(a) * x + cos(a) * y);
  }
  Vect& operator+=(const Vect& r) {
    x += r.x;
    y += r.y;
    return *this;
  }
  Vect& operator-=(const Vect& r) {
    x -= r.x;
    y -= r.y;
    return *this;
  }
  Vect& operator*=(double k) {
    x *= k;
    y *= k;
    return *this;
  }
  Vect& operator/=(double k) {
    x /= k;
    y /= k;
    return *this;
  }
  const Vect operator+(const Vect& r) const { return Vect(*this) += r; }
  const Vect operator-(const Vect& r) const { return Vect(*this) -= r; }
  const Vect operator*(double k) const { return Vect(*this) *= k; }
  const Vect operator/(double k) const { return Vect(*this) /= k; }
  friend const Vect operator*(double k, const Vect& r) { return r * k; }
};
class Line {
 public:
  Vect u, v;
  Line() {}
  Line(const Vect& u, const Vect& v) : u(u), v(v) {}
  Line(double x1, double y1, double x2, double y2) : u(x1, y1), v(x2, y2) {}
};
class Circle {
 public:
  Vect u;
  double r;
  Circle() : r(0) {}
  Circle(const Vect& u, double r) : u(u), r(r) {}
  Circle(double x, double y, double r) : u(x, y), r(r) {}
  operator bool() const { return u && gt(r, 0); }
};
bool plt(const Vect& u, const Vect& v) {
  return eq(u.dir(), v.dir()) ? lt(u.len(), v.len()) : lt(u.dir(), v.dir());
}
double pdf(const Vect& u, const Vect& v) {
  double a = v.dir() - u.dir();
  return a < 0 ? a + 2 * pi : a;
}
bool parallel(const Line& a, const Line& b) {
  return eq((a.u - a.v) * (b.u - b.v), 0);
}
bool vertical(const Line& a, const Line& b) {
  return eq((a.u - a.v) % (b.u - b.v), 0);
}
bool onBee(const Vect& p, const Line& l) {
  return eq((p - l.u) * (p - l.v), 0);
}
bool onRay(const Vect& p, const Line& l, bool flag = true) {
  return eq((p - l.u) * (p - l.v), 0) &&
         (flag ? ge : gt)((p - l.u) % (l.v - l.u), 0);
}
bool onSeg(const Vect& p, const Line& l, bool flag = true) {
  return eq((p - l.u) * (p - l.v), 0) &&
         (flag ? ge : gt)((p - l.u) % (l.v - p), 0);
}
bool onCircle(const Vect& p, const Circle& c) {
  return eq((p - c.u).len(), c.r);
}
bool inCircle(const Vect& p, const Circle& c, bool flag = true) {
  return (flag ? le : lt)((p - c.u).len(), c.r);
}
bool onPolygon(const Vect& p, const vector<Vect>& u) {
  for (int i = 1; i < int(u.size()); i++)
    if (onSeg(p, Line(u[i - 1], u[i]))) return true;
  return onSeg(p, Line(u.back(), u[0]));
}
bool inPolygon(const Vect& p, const vector<Vect>& u, bool flag = true) {
  if (onPolygon(p, u)) return flag;
  Vect t = u.back() - p;
  int s = 0, j = (t.x < 0) ^ (t.y < 0) * 3;
  for (int i = 0; i < int(u.size()); i++) {
    Vect r = u[i] - p;
    int k = (r.x < 0) ^ (r.y < 0) * 3;
    if (((j + 1) & 3) == k) s++;
    if (((k + 1) & 3) == j) s--;
    if ((j ^ k) == 2) s += (r * t < 0) * 4 - 2;
    t = r;
    j = k;
  }
  return s;
}
const Vect operator&(const Line& a, const Line& b) {
  double d = (a.u - a.v) * (b.u - b.v);
  if (eq(d, 0)) return Vect(na, na);
  double k = (a.u - b.u) * (b.u - b.v) / d;
  return a.u + (a.v - a.u) * k;
}
const Line operator&(const Line& l, const Circle& c) {
  static Line nl = Line(na, na, na, na);
  if (l.u == l.v) return onCircle(l.u, c) ? l : nl;
  Vect p = Line(c.u + (l.v - l.u).ort(), c.u) & l;
  double d = c.r * c.r - (p - c.u) % (p - c.u);
  if (le(d, 0)) return lt(d, 0) ? nl : Line(p, p);
  Vect t = sqrt(d) * ~(l.v - l.u);
  return Line(p - t, p + t);
}
const Line operator&(const Circle& c, const Line& l) { return l & c; }
const Line operator&(const Circle& a, const Circle& b) {
  Vect t = b.u - a.u;
  if (t == Vect(0, 0)) return Line(na, na, na, na);
  double k = 0.5 + (a.r * a.r - b.r * b.r) / (t % t) / 2;
  Vect p = a.u + t * k;
  return Line(p, p + t.ort()) & a;
}
const Vect symmetry(const Vect& p, const Vect& t) { return t + t - p; }
const Vect symmetry(const Vect& p, const Line& l) {
  return (Line(p, p + (l.v - l.u).ort()) & l) * 2.0 - p;
}
const vector<Vect> graham(const vector<Vect>& u, bool flag = true) {
  vector<Vect> r;
  for (int i = 0, k = 1, t = 1; ~i; i += t) {
    while (int(r.size()) > k) {
      Vect a = r.back() - r[r.size() - 2];
      Vect b = r.back() - u[i];
      if ((flag ? le : lt)(a * b, 0)) break;
      r.pop_back();
    }
    if (i == int(u.size()) - 1) k = r.size() - (t = -1);
    r.push_back(u[i]);
  }
  if (r.size() > 1) r.pop_back();
  return r;
}
string gao() {
  Line a[3];
  set<Vect> ep, cp, ec;
  for (int i = 0; i < 3; i++) {
    scanf("%lf%lf", &a[i].u.x, &a[i].u.y);
    scanf("%lf%lf", &a[i].v.x, &a[i].v.y);
    ep.insert(a[i].u);
    ep.insert(a[i].v);
  }
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < i; j++) {
      if (a[i].u == a[j].u && a[i].v == a[j].v ||
          a[i].u == a[j].v && a[i].v == a[j].u)
        return "NO";
    }
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < i; j++) {
      Vect t = a[i] & a[j];
      if (t && onSeg(t, a[i]) && onSeg(t, a[j])) cp.insert(t);
    }
  if (ep.size() != 5) return "NO";
  if (cp.size() != 3) return "NO";
  for (auto t : cp)
    if (!ep.count(t)) return "NO";
  for (int i = 0; i < 3; i++) {
    if (!cp.count(a[i].u) || !cp.count(a[i].v)) continue;
    int j = (i + 1) % 3, k = (i + 2) % 3;
    Vect p = a[i] & a[j], q = a[i] & a[k];
    if (!p || p == a[j].u || p == a[j].v || !q || q == a[k].u || q == a[k].v)
      continue;
    double x = (p - a[j].u).len() / (p - a[j].v).len();
    double y = (q - a[k].u).len() / (q - a[k].v).len();
    double r = 0;
    if (a[j].u == a[k].u) r = pdf(a[j].v - a[j].u, a[k].v - a[k].u);
    if (a[j].u == a[k].v) r = pdf(a[j].v - a[j].u, a[k].u - a[k].v);
    if (a[j].v == a[k].u) r = pdf(a[j].u - a[j].v, a[k].v - a[k].u);
    if (a[j].v == a[k].v) r = pdf(a[j].u - a[j].v, a[k].u - a[k].v);
    if (lt(x, 0.25) || gt(x, 4.0) || lt(y, 0.25) || gt(y, 4.0) ||
        gt(min(r, 2 * pi - r), pi / 2))
      return "NO";
    return "YES";
  }
  return "NO";
}
int main() {
  int cs;
  scanf("%d", &cs);
  while (cs--) printf("%s\n", gao().c_str());
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Little Petya learns how to write. The teacher gave pupils the task to write the letter A on the sheet of paper. It is required to check whether Petya really had written the letter A.

You are given three segments on the plane. They form the letter A if the following conditions hold:

  * Two segments have common endpoint (lets call these segments first and second), while the third segment connects two points on the different segments. 
  * The angle between the first and the second segments is greater than 0 and do not exceed 90 degrees. 
  * The third segment divides each of the first two segments in proportion not less than 1 / 4 (i.e. the ratio of the length of the shortest part to the length of the longest part is not less than 1 / 4). 

Input

The first line contains one integer t (1 ≤ t ≤ 10000) — the number of test cases to solve. Each case consists of three lines. Each of these three lines contains four space-separated integers — coordinates of the endpoints of one of the segments. All coordinates do not exceed 108 by absolute value. All segments have positive length.

Output

Output one line for each test case. Print «YES» (without quotes), if the segments form the letter A and «NO» otherwise.

Examples

Input

3
4 4 6 0
4 1 5 2
4 0 4 4
0 0 0 6
0 6 2 -4
1 1 0 1
0 0 0 5
0 5 2 -1
1 2 0 1


Output

YES
NO
YES

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using namespace rel_ops;
extern const double nil;
const double eps = 1e-8;
const double pi = 3.1415926535897932384626;
const double na = sqrt(-1);
const double inf = 1.0 / nil;
const double nil = 0.0;
inline bool lt(double a, double b) { return b - a >= eps; }
inline bool gt(double a, double b) { return a - b >= eps; }
inline bool le(double a, double b) { return a - b < eps; }
inline bool ge(double a, double b) { return b - a < eps; }
inline bool eq(double a, double b) { return le(a, b) && ge(a, b); }
inline bool ne(double a, double b) { return lt(a, b) || gt(a, b); }
class Vect {
 public:
  double x, y;
  Vect() : x(0), y(0) {}
  Vect(double x, double y) : x(x), y(y) {}
  operator bool() const { return x == x && y == y; }
  bool operator==(const Vect& r) const { return eq(x, r.x) && eq(y, r.y); }
  bool operator<(const Vect& r) const {
    return lt(x, r.x) || (eq(x, r.x) && lt(y, r.y));
  }
  double len() const { return sqrt(x * x + y * y); }
  double dir() const { return atan2(y, x); }
  double operator*(const Vect& r) const { return x * r.y - y * r.x; }
  double operator%(const Vect& r) const { return x * r.x + y * r.y; }
  const Vect operator-() const { return Vect(-x, -y); }
  const Vect operator~() const { return *this / len(); }
  const Vect ort() const { return Vect(-y, x); }
  const Vect rot(double a) const {
    return Vect(cos(a) * x - sin(a) * y, sin(a) * x + cos(a) * y);
  }
  Vect& operator+=(const Vect& r) {
    x += r.x;
    y += r.y;
    return *this;
  }
  Vect& operator-=(const Vect& r) {
    x -= r.x;
    y -= r.y;
    return *this;
  }
  Vect& operator*=(double k) {
    x *= k;
    y *= k;
    return *this;
  }
  Vect& operator/=(double k) {
    x /= k;
    y /= k;
    return *this;
  }
  const Vect operator+(const Vect& r) const { return Vect(*this) += r; }
  const Vect operator-(const Vect& r) const { return Vect(*this) -= r; }
  const Vect operator*(double k) const { return Vect(*this) *= k; }
  const Vect operator/(double k) const { return Vect(*this) /= k; }
  friend const Vect operator*(double k, const Vect& r) { return r * k; }
};
class Line {
 public:
  Vect u, v;
  Line() {}
  Line(const Vect& u, const Vect& v) : u(u), v(v) {}
  Line(double x1, double y1, double x2, double y2) : u(x1, y1), v(x2, y2) {}
};
class Circle {
 public:
  Vect u;
  double r;
  Circle() : r(0) {}
  Circle(const Vect& u, double r) : u(u), r(r) {}
  Circle(double x, double y, double r) : u(x, y), r(r) {}
  operator bool() const { return u && gt(r, 0); }
};
bool plt(const Vect& u, const Vect& v) {
  return eq(u.dir(), v.dir()) ? lt(u.len(), v.len()) : lt(u.dir(), v.dir());
}
double pdf(const Vect& u, const Vect& v) {
  double a = v.dir() - u.dir();
  return a < 0 ? a + 2 * pi : a;
}
bool parallel(const Line& a, const Line& b) {
  return eq((a.u - a.v) * (b.u - b.v), 0);
}
bool vertical(const Line& a, const Line& b) {
  return eq((a.u - a.v) % (b.u - b.v), 0);
}
bool onBee(const Vect& p, const Line& l) {
  return eq((p - l.u) * (p - l.v), 0);
}
bool onRay(const Vect& p, const Line& l, bool flag = true) {
  return eq((p - l.u) * (p - l.v), 0) &&
         (flag ? ge : gt)((p - l.u) % (l.v - l.u), 0);
}
bool onSeg(const Vect& p, const Line& l, bool flag = true) {
  return eq((p - l.u) * (p - l.v), 0) &&
         (flag ? ge : gt)((p - l.u) % (l.v - p), 0);
}
bool onCircle(const Vect& p, const Circle& c) {
  return eq((p - c.u).len(), c.r);
}
bool inCircle(const Vect& p, const Circle& c, bool flag = true) {
  return (flag ? le : lt)((p - c.u).len(), c.r);
}
bool onPolygon(const Vect& p, const vector<Vect>& u) {
  for (int i = 1; i < int(u.size()); i++)
    if (onSeg(p, Line(u[i - 1], u[i]))) return true;
  return onSeg(p, Line(u.back(), u[0]));
}
bool inPolygon(const Vect& p, const vector<Vect>& u, bool flag = true) {
  if (onPolygon(p, u)) return flag;
  Vect t = u.back() - p;
  int s = 0, j = (t.x < 0) ^ (t.y < 0) * 3;
  for (int i = 0; i < int(u.size()); i++) {
    Vect r = u[i] - p;
    int k = (r.x < 0) ^ (r.y < 0) * 3;
    if (((j + 1) & 3) == k) s++;
    if (((k + 1) & 3) == j) s--;
    if ((j ^ k) == 2) s += (r * t < 0) * 4 - 2;
    t = r;
    j = k;
  }
  return s;
}
const Vect operator&(const Line& a, const Line& b) {
  double d = (a.u - a.v) * (b.u - b.v);
  if (eq(d, 0)) return Vect(na, na);
  double k = (a.u - b.u) * (b.u - b.v) / d;
  return a.u + (a.v - a.u) * k;
}
const Line operator&(const Line& l, const Circle& c) {
  static Line nl = Line(na, na, na, na);
  if (l.u == l.v) return onCircle(l.u, c) ? l : nl;
  Vect p = Line(c.u + (l.v - l.u).ort(), c.u) & l;
  double d = c.r * c.r - (p - c.u) % (p - c.u);
  if (le(d, 0)) return lt(d, 0) ? nl : Line(p, p);
  Vect t = sqrt(d) * ~(l.v - l.u);
  return Line(p - t, p + t);
}
const Line operator&(const Circle& c, const Line& l) { return l & c; }
const Line operator&(const Circle& a, const Circle& b) {
  Vect t = b.u - a.u;
  if (t == Vect(0, 0)) return Line(na, na, na, na);
  double k = 0.5 + (a.r * a.r - b.r * b.r) / (t % t) / 2;
  Vect p = a.u + t * k;
  return Line(p, p + t.ort()) & a;
}
const Vect symmetry(const Vect& p, const Vect& t) { return t + t - p; }
const Vect symmetry(const Vect& p, const Line& l) {
  return (Line(p, p + (l.v - l.u).ort()) & l) * 2.0 - p;
}
const vector<Vect> graham(const vector<Vect>& u, bool flag = true) {
  vector<Vect> r;
  for (int i = 0, k = 1, t = 1; ~i; i += t) {
    while (int(r.size()) > k) {
      Vect a = r.back() - r[r.size() - 2];
      Vect b = r.back() - u[i];
      if ((flag ? le : lt)(a * b, 0)) break;
      r.pop_back();
    }
    if (i == int(u.size()) - 1) k = r.size() - (t = -1);
    r.push_back(u[i]);
  }
  if (r.size() > 1) r.pop_back();
  return r;
}
string gao() {
  Line a[3];
  set<Vect> ep, cp, ec;
  for (int i = 0; i < 3; i++) {
    scanf("%lf%lf", &a[i].u.x, &a[i].u.y);
    scanf("%lf%lf", &a[i].v.x, &a[i].v.y);
    ep.insert(a[i].u);
    ep.insert(a[i].v);
  }
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < i; j++) {
      if (a[i].u == a[j].u && a[i].v == a[j].v ||
          a[i].u == a[j].v && a[i].v == a[j].u)
        return "NO";
    }
  for (int i = 0; i < 3; i++)
    for (int j = 0; j < i; j++) {
      Vect t = a[i] & a[j];
      if (t && onSeg(t, a[i]) && onSeg(t, a[j])) cp.insert(t);
    }
  if (ep.size() != 5) return "NO";
  if (cp.size() != 3) return "NO";
  for (auto t : cp)
    if (!ep.count(t)) return "NO";
  for (int i = 0; i < 3; i++) {
    if (!cp.count(a[i].u) || !cp.count(a[i].v)) continue;
    int j = (i + 1) % 3, k = (i + 2) % 3;
    Vect p = a[i] & a[j], q = a[i] & a[k];
    if (!p || p == a[j].u || p == a[j].v || !q || q == a[k].u || q == a[k].v)
      continue;
    double x = (p - a[j].u).len() / (p - a[j].v).len();
    double y = (q - a[k].u).len() / (q - a[k].v).len();
    double r = 0;
    if (a[j].u == a[k].u) r = pdf(a[j].v - a[j].u, a[k].v - a[k].u);
    if (a[j].u == a[k].v) r = pdf(a[j].v - a[j].u, a[k].u - a[k].v);
    if (a[j].v == a[k].u) r = pdf(a[j].u - a[j].v, a[k].v - a[k].u);
    if (a[j].v == a[k].v) r = pdf(a[j].u - a[j].v, a[k].u - a[k].v);
    if (lt(x, 0.25) || gt(x, 4.0) || lt(y, 0.25) || gt(y, 4.0) ||
        gt(min(r, 2 * pi - r), pi / 2))
      return "NO";
    return "YES";
  }
  return "NO";
}
int main() {
  int cs;
  scanf("%d", &cs);
  while (cs--) printf("%s\n", gao().c_str());
}

```