32_E. Hide-and-Seek_9662
Victor and Peter are playing hide-and-seek. Peter has hidden, and Victor is to find him. In the room where they are playing, there is only one non-transparent wall and one double-sided mirror. Victor and Peter are points with coordinates (xv, yv) and (xp, yp) respectively. The wall is a segment joining points with coordinates (xw, 1, yw, 1) and (xw, 2, yw, 2), the mirror — a segment joining points (xm, 1, ym, 1) and (xm, 2, ym, 2).

If an obstacle has a common point with a line of vision, it's considered, that the boys can't see each other with this line of vision. If the mirror has a common point with the line of vision, it's considered, that the boys can see each other in the mirror, i.e. reflection takes place. The reflection process is governed by laws of physics — the angle of incidence is equal to the angle of reflection. The incident ray is in the same half-plane as the reflected ray, relative to the mirror. I.e. to see each other Victor and Peter should be to the same side of the line, containing the mirror (see example 1). If the line of vision is parallel to the mirror, reflection doesn't take place, and the mirror isn't regarded as an obstacle (see example 4).

Victor got interested if he can see Peter, while standing at the same spot. Help him solve this problem.

Input

The first line contains two numbers xv and yv — coordinates of Victor.

The second line contains two numbers xp and yp — coordinates of Peter.

The third line contains 4 numbers xw, 1, yw, 1, xw, 2, yw, 2 — coordinates of the wall.

The forth line contains 4 numbers xm, 1, ym, 1, xm, 2, ym, 2 — coordinates of the mirror.

All the coordinates are integer numbers, and don't exceed 104 in absolute value. It's guaranteed, that the segments don't have common points, Victor and Peter are not on any of the segments, coordinates of Victor and Peter aren't the same, the segments don't degenerate into points.

Output

Output YES, if Victor can see Peter without leaving the initial spot. Otherwise output NO.

Examples

Input

-1 3
1 3
0 2 0 4
0 0 0 1


Output

NO


Input

0 0
1 1
0 1 1 0
-100 -100 -101 -101


Output

NO


Input

0 0
1 1
0 1 1 0
-1 1 1 3


Output

YES


Input

0 0
10 0
100 100 101 101
1 0 3 0


Output

YES
#include <bits/stdc++.h>
using namespace std;
class vec {
 public:
  double x, y;
  vec() {}
  vec(double tx, double ty) { x = tx, y = ty; }
  vec operator+(const vec &t) { return vec(x + t.x, y + t.y); }
  vec operator-(const vec &t) { return vec(x - t.x, y - t.y); }
  double operator*(const vec &t) { return x * t.y - y * t.x; }
  double operator^(const vec &t) { return x * t.x + y * t.y; }
  double length() { return sqrt(x * x + y * y); }
  bool operator==(const vec &t) {
    return fabs(x - t.x) <= 1e-6 && fabs(y - t.y) <= 1e-6;
  }
  bool operator!=(const vec &t) { return !(*this == t); }
  vec operator/(const double &t) { return vec(x / t, y / t); }
} alice, bob;
class seg {
 public:
  vec st, ed;
  seg() {}
  seg(vec a, vec b) { st = a, ed = b; }
} wall, mirror;
bool issq(seg a, seg b) {
  vec &p1 = a.st, &p2 = a.ed, &q1 = b.st, &q2 = b.ed;
  bool ret = min(p1.x, p2.x) <= max(q1.x, q2.x) &&
             min(q1.x, q2.x) <= max(p1.x, p2.x) &&
             min(p1.y, p2.y) <= max(q1.y, q2.y) &&
             min(q1.y, q2.y) <= max(p1.y, p2.y);
  return ret;
}
bool crosstest(seg a, seg b) {
  return ((b.st - a.st) * (a.ed - a.st)) * ((b.ed - a.st) * (a.ed - a.st)) <=
         1e-6;
}
bool intersect(seg a, seg b) {
  return issq(a, b) && crosstest(a, b) && crosstest(b, a);
}
vec reflect(vec a, seg b) {
  vec A = a - b.st, B = b.ed - b.st;
  double cs = (A ^ B) / (A.length() * B.length());
  double sn = sqrt(1 - cs * cs);
  vec out =
      vec(B.x * cs - B.y * sn, B.x * sn + B.y * cs) / (B.length() / A.length());
  if (out != A) return b.st + out;
  out = vec(B.x * cs + B.y * sn, -B.x * sn + B.y * cs) /
        (B.length() / A.length());
  return b.st + out;
}
int main() {
  scanf("%lf%lf%lf%lf", &alice.x, &alice.y, &bob.x, &bob.y);
  scanf("%lf%lf%lf%lf", &wall.st.x, &wall.st.y, &wall.ed.x, &wall.ed.y);
  scanf("%lf%lf%lf%lf", &mirror.st.x, &mirror.st.y, &mirror.ed.x, &mirror.ed.y);
  if (!intersect(seg(alice, bob), wall) &&
      !intersect(seg(alice, bob), mirror)) {
    puts("YES");
    return 0;
  }
  vec alice2 = reflect(alice, mirror), bob2 = reflect(bob, mirror);
  if (intersect(seg(alice2, bob), mirror)) {
    if (!intersect(seg(alice2, bob), wall) &&
        !intersect(seg(alice, bob2), wall)) {
      puts("YES");
      return 0;
    }
  }
  puts("NO");
  return 0;
}

0 0
10 0
100 100 101 101
1 0 3 0
 -1 3
1 3
0 2 0 4
0 0 0 1
 0 0
1 1
0 1 1 0
-100 -100 -101 -101
 0 0
1 1
0 1 1 0
-1 1 1 3
 9293 -6547
4895 -9479
2738 -1395 8489 -8324
3540 -4860 -8555 1675
 -8193 -8833
4353 -8260
2214 683 -8074 -8978
5548 -850 -1486 -8372
 0 0
2 0
1 1 1 -1
-10 2 -12 2
 0 0
10 0
0 1 10 1
1 0 9 0
 3680 2196
8736 8904
7532 2465 3709 -8961
6439 -765 3053 3026
 3874 -278
-8905 -3524
-1544 -3249 4063 -111
-59 1361 7173 -847
 5023 -2243
5648 1799
1758 9228 -5815 3403
-5967 -5718 -9900 -7956
 1462 5132
-8664 2428
175 -8258 -9863 8483
-5685 3527 1556 5387
 -3234 2278
-1683 1276
-8143 -2879 -903 2275
9053 -2468 7486 6408
 -1971 -1636
8799 -5185
2406 2302 1967 -7166
-4122 5320 7348 337
 866 4303
-2945 -7242
-8638 4653 -1155 -7439
-950 -5491 2786 3812
 -5289 7185
-5026 4568
9256 -429 -3131 4617
-7143 -6595 -5505 -370
 0 0
2 0
1 1 1 -1
0 2 2 2
 7806 5101
9823 8971
-6640 -300 9044 7390
-2297 -3829 7806 2982
 0 0
3 0
1 0 2 0
-10 2 -12 2
 -8836 -5283
-5804 9454
-4442 76 -9550 -986
-5178 -982 -7763 -7108
 3261 2610
-701 -7693
6272 9652 -506 6144
-322 -4315 -1436 -2142
 -1541 -7140
-3434 7016
-831 6470 -4500 2354
-5503 -553 -5998 6361
 97 -43
7213 -4204
5460 -8068 4212 -2411
9853 -8477 7807 6052
 6777 -4260
1717 5583
3262 248 5800 1524
9267 -7380 8541 5269
 2696 -4753
-3435 -7793
4265 5958 -3218 -8692
4458 4449 4175 1539
 5108 2348
9100 7679
-7980 640 -4064 -8379
1883 -5793 9041 8957
 -7779 -1832
8313 7354
9767 8430 -8438 -3487
3855 4077 1085 -5181
 -7366 1446
-7727 -754
-2680 -3822 -5191 -5553
-7304 -6313 -9229 1377
 5851 7882
-6171 -4174
-1463 5985 4956 -8663
6370 -9777 -864 9154
 4646 5596
-2993 766
2443 -3831 3479 5022
-1987 4342 9668 7192
 362 9742
7948 7786
303 6095 -7816 9199
5875 7686 6702 6871
 0 0
5 0
1 0 2 0
3 0 4 0
 3336 -9832
-9350 -9113
-939 3907 -3643 -9931
8186 6365 6202 6802
 5286 518
-8906 -4274
-2162 1352 -751 -3408
-3469 2291 -9521 -462
 -1 2
1 2
0 2 0 4
0 0 0 1
 7111 8313
-4946 -9411
672 -5310 -7733 -1889
378 8589 -915 7675
 0 0
2 0
0 2 2 2
1 1 1 -1
 0 0
2 0
0 2 2 2
1 1 1 0
 3205 -9947
7374 -5260
-3110 3073 5060 -2488
7958 -5755 -7406 -816
 6161 -4520
-5630 -3171
-7760 9489 -9477 -630
9758 7404 -4730 -8056
 -3802 -741
-9954 6119
-1364 -1523 -8659 2791
6451 -4606 -7143 2288
 5974 2044
8371 6409
-675 4290 -8517 -9542
-9005 4263 -9763 -8777
 0 0
2 0
1 1 1 -1
1 2 2 2
 0 0
3 0
0 2 2 2
1 0 2 0
 1307 5392
3305 -837
-8550 -7782 5287 1042
-2922 -287 8944 3865
 4156 -5659
-9903 3069
-5545 1857 2358 4566
4920 4225 5236 7868
 0 0
1 1
100 100 101 101
-100 -100 -101 -101
 2729 -5812
9733 574
9967 3682 -9868 3984
9477 9254 2347 3997
 -7086 -8767
6803 2015
6175 -6560 3372 573
256 3769 393 9678
 -4752 -3262
-4582 6436
-8997 -6490 -4630 1426
-9865 -6697 -2371 -5622
 0 0
2 0
0 2 2 2
1 0 1 -1
 -1311 2310
2764 1131
-1964 -5465 -199 2630
-5664 9644 9110 2262
 -6319 2768
-431 5862
-5417 8036 -5331 3150
2385 -1888 3450 7359
 -3417 8449
7996 3499
3163 7949 5262 4575
1340 -17 -3934 8703
 2001 2179
-1925 -2455
7858 948 71 2256
4850 9947 1159 2295
 1772 9009
-8123 3429
-1873 9437 -2887 -997
8018 -9250 -5090 -9980
 -3107 -7674
4815 780
-4957 3486 1980 -2625
-432 -4075 -9497 -171
 9060 4628
5720 -2370
-1791 9325 1552 -3684
-161 -4597 2287 -3890
 -4496 6192
-8443 7736
2227 9746 -7197 6992
-4002 -6638 7315 -9557
 -8607 4167
4114 -152
3668 -1725 -7827 4541
-5338 9216 880 9081
 -8188 -5684
3623 46
3288 -265 5839 7672
2776 1685 2632 -7636
 5498 9900
7010 -7756
-7598 8619 -7166 -3069
-7486 -727 -9707 7115
 7880 -7342
1175 7552
-6177 6690 6086 -2763
6149 -2325 8602 -8496
 -1 2
1 2
0 3 0 4
0 0 0 2
 -1 5
1 5
0 2 0 4
0 0 0 1
 1184 -3127
-7123 6985
-1943 6259 1154 -4026
-4205 -4033 -5160 -4115
 -8240 -4453
8478 -878
7033 7520 -1002 -3146
-9913 8035 -9876 -8757
 -1 4
1 4
0 2 0 4
0 0 0 1
 -823 -3132
-1924 -8397
3277 5496 -1772 -6699
-5322 -4634 922 182
 -1541 -7140
-3434 7016
-831 6470 -7233 -5530
-5503 -553 -5998 6361
 -1 1
1 1
0 3 0 4
0 0 0 2
 0 0
2 0
1 1 1 -1
0 2 1 2
 4632 -9795
7738 -6486
1377 1248 1007 -1906
3402 9216 250 6991
 -7267 -975
-7760 5217
-9341 -5054 -7370 3072
-4926 1220 7603 -1721
 5567 -9695
5625 2216
1965 -7804 8129 -7554
1665 -446 5340 7652
 509 -7077
1396 9890
1192 2964 -1072 -8932
-3260 -6877 -1781 1603
 0 0
3 0
1 0 2 0
0 2 2 2
 -9867 3736
2889 5086
2601 -5285 -8930 4748
-3752 511 3554 1104
 -2389 53
-9955 5368
-4775 -593 7898 -2157
6659 1403 9634 -3275
 9293 -6547
4895 -9479
2738 -1395 8489 -8324
3540 -9426 -8555 1675
 0 0
10 0
0 1 10 1
2 0 9 0
 -8193 -8833
4353 -8260
2214 663 -8074 -8978
5548 -850 -1486 -8372
 0 -1
2 0
1 1 1 -1
-10 2 -12 2
 3680 186
8736 8904
7532 2465 3709 -8961
6439 -765 3053 3026
 3874 -278
-8905 -3524
-1544 -3249 4063 -111
-59 2646 7173 -847
 5023 -2243
5648 1799
1758 9640 -5815 3403
-5967 -5718 -9900 -7956
 1462 5132
-8664 2428
175 -8258 -9863 8483
-3683 3527 1556 5387
 -3234 2278
-1683 2102
-8143 -2879 -903 2275
9053 -2468 7486 6408
 -1971 -1636
8799 -5185
2406 2302 1967 -7166
-4122 5320 7348 187
 866 4303
-2945 -7242
-8638 4653 -1155 -7439
-1053 -5491 2786 3812
 -5289 7185
-5026 4568
9256 -429 -3131 4617
-7143 -6595 -9152 -370
 0 0
2 0
1 1 1 -2
0 2 2 2
 7806 5101
9823 8971
-6640 -300 9044 7390
-4305 -3829 7806 2982
 -8836 -5283
-5804 9454
-4442 76 -9550 -986
-5178 -982 -476 -7108
 3261 2610
-701 -7595
6272 9652 -506 6144
-322 -4315 -1436 -2142
 -1541 -7140
-3434 7016
-126 6470 -4500 2354
-5503 -553 -5998 6361
 97 -43
7213 -4204
5460 -9240 4212 -2411
9853 -8477 7807 6052
 6777 -4260
1717 5583
3262 248 405 1524
9267 -7380 8541 5269
 2696 -4753
-3435 -7793
4265 8496 -3218 -8692
4458 4449 4175 1539
 5108 2348
9100 7679
-7980 640 -4064 -8379
1883 -5793 14617 8957
 -7779 -1832
8313 7354
9767 8717 -8438 -3487
3855 4077 1085 -5181
 -7366 1446
-7727 -1428
-2680 -3822 -5191 -5553
-7304 -6313 -9229 1377
 5851 7882
-4881 -4174
-1463 5985 4956 -8663
6370 -9777 -864 9154
 4646 2452
-2993 766
2443 -3831 3479 5022
-1987 4342 9668 7192
 362 9742
7948 7786
303 6095 -7816 9199
5875 7686 6702 5774
 0 1
5 0
1 0 2 0
3 0 4 0
 3336 -9832
-9350 -9113
-939 3907 -3643 -9931
8186 6365 6202 4341
 5286 518
-8906 -4274
-2162 1972 -751 -3408
-3469 2291 -9521 -462
 -1 2
1 2
0 2 0 7
0 0 0 1
 11601 8313
-4946 -9411
672 -5310 -7733 -1889
378 8589 -915 7675
 0 0
2 0
0 3 2 2
1 1 1 -1
 0 0
3 0
0 2 2 2
1 1 1 0
 3205 -9947
7374 -5260
-2077 3073 5060 -2488
7958 -5755 -7406 -816
 6161 -4520
-5630 -412
-7760 9489 -9477 -630
9758 7404 -4730 -8056
 -3802 -741
-9954 6119
-1364 -1523 -8659 2791
6451 -4606 -1255 2288
 5974 106
8371 6409
-675 4290 -8517 -9542
-9005 4263 -9763 -8777
 0 0
2 0
1 1 1 -1
1 2 2 3
 0 0
4 0
0 2 2 2
1 0 2 0
 1307 5392
3305 -837
-8550 -7782 5287 1042
-2922 -287 8944 5794
 4156 -5659
-9903 3069
-4043 1857 2358 4566
4920 4225 5236 7868
 2163 -5812
9733 574
9967 3682 -9868 3984
9477 9254 2347 3997
 -7086 -9715
6803 2015
6175 -6560 3372 573
256 3769 393 9678
 -4752 -3262
-4582 6436
-8997 -6490 -4630 1426
-9865 -3168 -2371 -5622
 0 0
2 0
0 2 2 3
1 0 1 -1
 -1311 335
2764 1131
-1964 -5465 -199 2630
-5664 9644 9110 2262
 -8573 2768
-431 5862
-5417 8036 -5331 3150
2385 -1888 3450 7359
 -3417 8449
7996 3499
3163 7949 5262 4575
1340 -17 -729 8703
 2001 2179
-1925 -2455
7858 948 71 2256
4850 9947 1159 1605
 1772 9009
-8123 3429
-1873 9437 -2887 -997
8018 -9250 -6505 -9980
 -3107 -7674
4815 780
-730 3486 1980 -2625
-432 -4075 -9497 -171
 10185 4628
5720 -2370
-1791 9325 1552 -3684
-161 -4597 2287 -3890
 -4496 6192
-8443 7736
490 9746 -7197 6992
-4002 -6638 7315 -9557
 -8607 4167
4114 -152
3807 -1725 -7827 4541
-5338 9216 880 9081
 -8188 -5684
3623 46
3288 -265 5839 7672
2776 1685 2086 -7636
 5498 9900
7010 -7756
-7598 8619 -7166 -3069
-7486 -971 -9707 7115
 7880 -7342
1175 7552
-6177 6690 6086 -2763
6149 -2473 8602 -8496
 -1 2
1 2
0 3 0 4
-1 0 0 2
 -1 5
1 5
0 0 0 4
0 0 0 1
 1184 -3127
-7123 6985
-1943 6259 1154 -4026
-4205 -3247 -5160 -4115

YES NO NO YES NO NO NO YES NO NO YES NO YES NO NO YES YES NO NO NO YES YES YES YES NO NO NO YES NO YES YES NO NO YES NO NO NO NO NO NO NO YES YES YES NO YES YES YES NO YES NO YES YES YES NO YES NO YES NO YES NO YES YES NO YES NO NO NO YES NO NO YES YES NO NO NO YES NO YES NO
 YES
 NO
 NO
 NO
 NO
 YES
 NO
 YES
 NO
 NO
 YES
 YES
 NO
 NO
 YES
 YES
 YES
 YES
 NO
 YES
 NO
 YES
 NO
 NO
 YES
 YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
 NO
 YES
 NO
 YES
 YES
 NO
 NO
 NO
 NO
 NO
 NO
 NO
 YES
 NO
 YES
 NO
 YES
 NO
 YES
 YES
 NO
 YES
 NO
