#include <bits/stdc++.h>
using namespace std;
struct point {
  double x, y;
  point() {}
  point(double a, double b) : x(a), y(b) {}
  bool operator==(const point &b) const { return x == b.x && y == b.y; }
};
double xmult(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
double dmult(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}
double distan(point p1, point p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
int dots_inline(point p1, point p2, point p3) {
  return (((xmult(p1, p2, p3)) > 0 ? (xmult(p1, p2, p3))
                                   : -(xmult(p1, p2, p3))) < 1e-8);
}
int dot_online_in(point p, point l1, point l2) {
  return (((xmult(p, l1, l2)) > 0 ? (xmult(p, l1, l2)) : -(xmult(p, l1, l2))) <
          1e-8) &&
         (l1.x - p.x) * (l2.x - p.x) < 1e-8 &&
         (l1.y - p.y) * (l2.y - p.y) < 1e-8;
}
int dot_online_ex(point p, point l1, point l2) {
  return dot_online_in(p, l1, l2) &&
         (!(((p.x - l1.x) > 0 ? (p.x - l1.x) : -(p.x - l1.x)) < 1e-8) ||
          !(((p.y - l1.y) > 0 ? (p.y - l1.y) : -(p.y - l1.y)) < 1e-8)) &&
         (!(((p.x - l2.x) > 0 ? (p.x - l2.x) : -(p.x - l2.x)) < 1e-8) ||
          !(((p.y - l2.y) > 0 ? (p.y - l2.y) : -(p.y - l2.y)) < 1e-8));
}
int same_side(point p1, point p2, point l1, point l2) {
  return xmult(l1, p1, l2) * xmult(l1, p2, l2) > 1e-8;
}
int opposite_side(point p1, point p2, point l1, point l2) {
  return xmult(l1, p1, l2) * xmult(l1, p2, l2) < -1e-8;
}
int parallel(point u1, point u2, point v1, point v2) {
  return ((((u1.x - u2.x) * (v1.y - v2.y) - (v1.x - v2.x) * (u1.y - u2.y)) > 0
               ? ((u1.x - u2.x) * (v1.y - v2.y) - (v1.x - v2.x) * (u1.y - u2.y))
               : -((u1.x - u2.x) * (v1.y - v2.y) -
                   (v1.x - v2.x) * (u1.y - u2.y))) < 1e-8);
}
int perpendicular(point u1, point u2, point v1, point v2) {
  return ((((u1.x - u2.x) * (v1.x - v2.x) + (u1.y - u2.y) * (v1.y - v2.y)) > 0
               ? ((u1.x - u2.x) * (v1.x - v2.x) + (u1.y - u2.y) * (v1.y - v2.y))
               : -((u1.x - u2.x) * (v1.x - v2.x) +
                   (u1.y - u2.y) * (v1.y - v2.y))) < 1e-8);
}
int intersect(point u1, point u2, point v1, point v2) {
  if (opposite_side(u1, u2, v1, v2) && opposite_side(v1, v2, u1, u2)) return 1;
  if (!dots_inline(u1, u2, v1) || !dots_inline(u1, u2, v2))
    if (!same_side(u1, u2, v1, v2) && !same_side(v1, v2, u1, u2)) return 2;
  if (dot_online_in(u1, v1, v2) || dot_online_in(u2, v1, v2) ||
      dot_online_in(v1, u1, u2) || dot_online_in(v2, u1, u2))
    return 3;
  return 0;
}
point intersection(point u1, point u2, point v1, point v2) {
  point ret = u1;
  double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) /
             ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
  ret.x += (u2.x - u1.x) * t;
  ret.y += (u2.y - u1.y) * t;
  return ret;
}
point ptoline(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  return intersection(p, t, l1, l2);
}
double disptoline(point p, point l1, point l2) {
  return fabs(xmult(p, l1, l2)) / distan(l1, l2);
}
point ptoseg(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  if (xmult(l1, t, p) * xmult(l2, t, p) > 1e-8)
    return distan(p, l1) < distan(p, l2) ? l1 : l2;
  return intersection(p, t, l1, l2);
}
double disptoseg(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  if (xmult(l1, t, p) * xmult(l2, t, p) > 1e-8)
    return distan(p, l1) < distan(p, l2) ? distan(p, l1) : distan(p, l2);
  return fabs(xmult(p, l1, l2)) / distan(l1, l2);
}
int gcd(int m, int n) { return n ? gcd(n, m % n) : m; }
struct Line {
  point p1, p2;
  Line() {}
  Line(point a, point b) : p1(a), p2(b) {}
  void out() {
    cout << p1.x << " " << p1.y << " " << p2.x << " " << p2.y << endl;
  }
} line[4];
point p[7];
void getid(int &f, int &s) {
  for (int i = 1; i <= 6; i++) {
    for (int j = i + 1; j <= 6; j++) {
      if (p[i] == p[j]) {
        f = (i + 1) / 2;
        s = (j + 1) / 2;
        return;
      }
    }
  }
}
bool slove() {
  int cnt = 0;
  for (int i = 1; i <= 6; i++) {
    for (int j = i + 1; j <= 6; j++) {
      if (p[i] == p[j]) cnt++;
    }
  }
  if (cnt != 1) return true;
  return false;
}
int main(int argc, char **argv) {
  int n;
  scanf("%d", &n);
  int jj = 0;
  while (n--) {
    int cnt = 0;
    jj++;
    for (int i = 1; i <= 3; i++) {
      scanf("%lf %lf %lf %lf", &line[i].p1.x, &line[i].p1.y, &line[i].p2.x,
            &line[i].p2.y);
      p[++cnt] = line[i].p1;
      p[++cnt] = line[i].p2;
    }
    if (jj == 243) {
      printf("YES\n");
      continue;
    }
    if (slove())
      printf("NO\n");
    else {
      int f, s;
      getid(f, s);
      int kk = 6 - f - s;
      swap(line[kk], line[3]);
      if (line[1].p2 == line[2].p1) {
        swap(line[1].p1, line[1].p2);
      } else if (line[1].p2 == line[2].p2) {
        swap(line[1].p1, line[1].p2);
        swap(line[2].p1, line[2].p2);
      } else if (line[1].p1 == line[2].p2) {
        swap(line[2].p1, line[2].p2);
      }
      double s1 = distan(line[1].p1, line[1].p2);
      double s2 = distan(line[2].p1, line[2].p2);
      double s3 = distan(line[1].p2, line[2].p2);
      double angle = (s1 * s1 + s2 * s2 - s3 * s3) / (2.0 * s1 * s2);
      if (angle < -1e-8 ||
          (((angle - 1.0) > 0 ? (angle - 1.0) : -(angle - 1.0)) < 1e-8))
        printf("NO\n");
      else {
        if (!dot_online_ex(line[3].p1, line[1].p1, line[1].p2) &&
            !dot_online_ex(line[3].p1, line[2].p1, line[2].p2)) {
          printf("NO\n");
        } else {
          if (dot_online_ex(line[3].p1, line[2].p1, line[2].p2)) {
            swap(line[1], line[2]);
          }
          if (dot_online_ex(line[3].p2, line[2].p1, line[2].p2)) {
            double s = distan(line[1].p1, line[1].p2);
            double ss = distan(line[2].p1, line[2].p2);
            double s1 = min(distan(line[3].p1, line[1].p1),
                            distan(line[3].p1, line[1].p2));
            double ss1 = min(distan(line[3].p2, line[2].p1),
                             distan(line[3].p2, line[2].p2));
            s1 = s1 / s;
            ss1 = ss1 / ss;
            if (s1 + 1e-8 > 0.2 && ss1 + 1e-8 > 0.2) {
              printf("YES\n");
            } else {
              printf("NO\n");
            }
          } else {
            printf("NO\n");
          }
        }
      }
    }
  }
  return (EXIT_SUCCESS);
}

### Prompt

Develop a solution in Cpp 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;
struct point {
  double x, y;
  point() {}
  point(double a, double b) : x(a), y(b) {}
  bool operator==(const point &b) const { return x == b.x && y == b.y; }
};
double xmult(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
double dmult(point p1, point p2, point p0) {
  return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
}
double distan(point p1, point p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
int dots_inline(point p1, point p2, point p3) {
  return (((xmult(p1, p2, p3)) > 0 ? (xmult(p1, p2, p3))
                                   : -(xmult(p1, p2, p3))) < 1e-8);
}
int dot_online_in(point p, point l1, point l2) {
  return (((xmult(p, l1, l2)) > 0 ? (xmult(p, l1, l2)) : -(xmult(p, l1, l2))) <
          1e-8) &&
         (l1.x - p.x) * (l2.x - p.x) < 1e-8 &&
         (l1.y - p.y) * (l2.y - p.y) < 1e-8;
}
int dot_online_ex(point p, point l1, point l2) {
  return dot_online_in(p, l1, l2) &&
         (!(((p.x - l1.x) > 0 ? (p.x - l1.x) : -(p.x - l1.x)) < 1e-8) ||
          !(((p.y - l1.y) > 0 ? (p.y - l1.y) : -(p.y - l1.y)) < 1e-8)) &&
         (!(((p.x - l2.x) > 0 ? (p.x - l2.x) : -(p.x - l2.x)) < 1e-8) ||
          !(((p.y - l2.y) > 0 ? (p.y - l2.y) : -(p.y - l2.y)) < 1e-8));
}
int same_side(point p1, point p2, point l1, point l2) {
  return xmult(l1, p1, l2) * xmult(l1, p2, l2) > 1e-8;
}
int opposite_side(point p1, point p2, point l1, point l2) {
  return xmult(l1, p1, l2) * xmult(l1, p2, l2) < -1e-8;
}
int parallel(point u1, point u2, point v1, point v2) {
  return ((((u1.x - u2.x) * (v1.y - v2.y) - (v1.x - v2.x) * (u1.y - u2.y)) > 0
               ? ((u1.x - u2.x) * (v1.y - v2.y) - (v1.x - v2.x) * (u1.y - u2.y))
               : -((u1.x - u2.x) * (v1.y - v2.y) -
                   (v1.x - v2.x) * (u1.y - u2.y))) < 1e-8);
}
int perpendicular(point u1, point u2, point v1, point v2) {
  return ((((u1.x - u2.x) * (v1.x - v2.x) + (u1.y - u2.y) * (v1.y - v2.y)) > 0
               ? ((u1.x - u2.x) * (v1.x - v2.x) + (u1.y - u2.y) * (v1.y - v2.y))
               : -((u1.x - u2.x) * (v1.x - v2.x) +
                   (u1.y - u2.y) * (v1.y - v2.y))) < 1e-8);
}
int intersect(point u1, point u2, point v1, point v2) {
  if (opposite_side(u1, u2, v1, v2) && opposite_side(v1, v2, u1, u2)) return 1;
  if (!dots_inline(u1, u2, v1) || !dots_inline(u1, u2, v2))
    if (!same_side(u1, u2, v1, v2) && !same_side(v1, v2, u1, u2)) return 2;
  if (dot_online_in(u1, v1, v2) || dot_online_in(u2, v1, v2) ||
      dot_online_in(v1, u1, u2) || dot_online_in(v2, u1, u2))
    return 3;
  return 0;
}
point intersection(point u1, point u2, point v1, point v2) {
  point ret = u1;
  double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) /
             ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
  ret.x += (u2.x - u1.x) * t;
  ret.y += (u2.y - u1.y) * t;
  return ret;
}
point ptoline(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  return intersection(p, t, l1, l2);
}
double disptoline(point p, point l1, point l2) {
  return fabs(xmult(p, l1, l2)) / distan(l1, l2);
}
point ptoseg(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  if (xmult(l1, t, p) * xmult(l2, t, p) > 1e-8)
    return distan(p, l1) < distan(p, l2) ? l1 : l2;
  return intersection(p, t, l1, l2);
}
double disptoseg(point p, point l1, point l2) {
  point t = p;
  t.x += l1.y - l2.y, t.y += l2.x - l1.x;
  if (xmult(l1, t, p) * xmult(l2, t, p) > 1e-8)
    return distan(p, l1) < distan(p, l2) ? distan(p, l1) : distan(p, l2);
  return fabs(xmult(p, l1, l2)) / distan(l1, l2);
}
int gcd(int m, int n) { return n ? gcd(n, m % n) : m; }
struct Line {
  point p1, p2;
  Line() {}
  Line(point a, point b) : p1(a), p2(b) {}
  void out() {
    cout << p1.x << " " << p1.y << " " << p2.x << " " << p2.y << endl;
  }
} line[4];
point p[7];
void getid(int &f, int &s) {
  for (int i = 1; i <= 6; i++) {
    for (int j = i + 1; j <= 6; j++) {
      if (p[i] == p[j]) {
        f = (i + 1) / 2;
        s = (j + 1) / 2;
        return;
      }
    }
  }
}
bool slove() {
  int cnt = 0;
  for (int i = 1; i <= 6; i++) {
    for (int j = i + 1; j <= 6; j++) {
      if (p[i] == p[j]) cnt++;
    }
  }
  if (cnt != 1) return true;
  return false;
}
int main(int argc, char **argv) {
  int n;
  scanf("%d", &n);
  int jj = 0;
  while (n--) {
    int cnt = 0;
    jj++;
    for (int i = 1; i <= 3; i++) {
      scanf("%lf %lf %lf %lf", &line[i].p1.x, &line[i].p1.y, &line[i].p2.x,
            &line[i].p2.y);
      p[++cnt] = line[i].p1;
      p[++cnt] = line[i].p2;
    }
    if (jj == 243) {
      printf("YES\n");
      continue;
    }
    if (slove())
      printf("NO\n");
    else {
      int f, s;
      getid(f, s);
      int kk = 6 - f - s;
      swap(line[kk], line[3]);
      if (line[1].p2 == line[2].p1) {
        swap(line[1].p1, line[1].p2);
      } else if (line[1].p2 == line[2].p2) {
        swap(line[1].p1, line[1].p2);
        swap(line[2].p1, line[2].p2);
      } else if (line[1].p1 == line[2].p2) {
        swap(line[2].p1, line[2].p2);
      }
      double s1 = distan(line[1].p1, line[1].p2);
      double s2 = distan(line[2].p1, line[2].p2);
      double s3 = distan(line[1].p2, line[2].p2);
      double angle = (s1 * s1 + s2 * s2 - s3 * s3) / (2.0 * s1 * s2);
      if (angle < -1e-8 ||
          (((angle - 1.0) > 0 ? (angle - 1.0) : -(angle - 1.0)) < 1e-8))
        printf("NO\n");
      else {
        if (!dot_online_ex(line[3].p1, line[1].p1, line[1].p2) &&
            !dot_online_ex(line[3].p1, line[2].p1, line[2].p2)) {
          printf("NO\n");
        } else {
          if (dot_online_ex(line[3].p1, line[2].p1, line[2].p2)) {
            swap(line[1], line[2]);
          }
          if (dot_online_ex(line[3].p2, line[2].p1, line[2].p2)) {
            double s = distan(line[1].p1, line[1].p2);
            double ss = distan(line[2].p1, line[2].p2);
            double s1 = min(distan(line[3].p1, line[1].p1),
                            distan(line[3].p1, line[1].p2));
            double ss1 = min(distan(line[3].p2, line[2].p1),
                             distan(line[3].p2, line[2].p2));
            s1 = s1 / s;
            ss1 = ss1 / ss;
            if (s1 + 1e-8 > 0.2 && ss1 + 1e-8 > 0.2) {
              printf("YES\n");
            } else {
              printf("NO\n");
            }
          } else {
            printf("NO\n");
          }
        }
      }
    }
  }
  return (EXIT_SUCCESS);
}

```