191 WA: Please try these inputs if you have AC

[S.H.Bouwhuis]

I have found 74 different inputs here on the boards, and all of them are correct for my program. Unfortunately, I still get WA.

Could someone with AC please try the following inputs?

Code: Select all

500
-5 4 -3 3 4 1 -2 -4
-2 0 2 4 0 0 -1 1
1 -3 -8 -6 -3 3 3 -4
-8 -3 10 1 -5 5 3 0
0 -1 -8 -7 3 0 1 2
0 -2 -2 7 -1 0 -4 -2
-5 10 1 7 -5 3 3 0
0 9 8 -5 -1 1 -1 -1
0 0 1 4 4 0 3 -2
-3 3 7 -1 -1 -1 4 -1
2 -6 -10 -4 3 -1 -3 4
-3 3 -5 -2 -5 2 -2 -1
-2 1 0 -7 4 4 0 5
-5 9 6 1 -1 -2 0 -5
8 9 8 8 1 -2 -3 1
0 -9 0 -8 5 5 3 5
7 -3 3 -7 3 3 4 5
-8 10 -4 -5 -4 -2 -1 -5
5 -3 7 -2 -3 1 5 4
-9 -9 -8 -7 2 -4 5 -5
-6 -3 8 5 -5 0 -5 1
-1 7 -4 -6 5 0 4 2
6 1 4 -1 0 -2 -4 0
2 -7 0 7 0 2 4 0
3 -8 9 4 5 0 0 0
6 2 -3 -9 -4 -5 -1 -1
0 -4 -7 0 3 4 -4 -3
-1 -10 6 5 3 0 -3 0
-7 -7 7 -3 1 5 2 -4
8 -4 -8 -1 -4 5 4 5
-7 -9 -8 7 5 -2 5 4
2 -5 -10 3 -1 0 2 -3
3 -10 1 8 -5 1 2 -4
-6 -6 6 1 1 1 5 4
-1 8 -9 6 -5 0 2 5
-7 0 1 -9 -3 -2 -2 -4
10 -9 10 -3 1 1 1 5
2 1 -8 9 1 5 -2 -3
-2 0 8 2 1 -4 4 -1
-1 -8 7 -4 5 -4 4 -5
-3 4 -6 -10 -5 5 1 -1
5 -2 0 -2 2 -2 -5 3
-3 2 -8 -6 -1 4 -1 -2
1 5 5 1 4 -2 -5 2
0 -4 8 7 5 3 -5 -3
-8 -5 -2 0 5 2 -1 0
10 -9 10 -4 1 -3 1 -5
1 2 6 -2 5 4 5 3
-1 6 -10 3 5 -3 1 -2
9 10 -9 -2 0 1 0 4
-10 3 3 3 5 -5 1 5
-4 6 0 10 3 0 5 -2
-6 -8 -1 -3 -5 -5 -3 2
-6 1 4 1 5 1 -5 -1
3 2 -6 0 2 -4 5 -2
-3 -8 8 5 0 5 4 0
10 -4 -10 -4 -5 3 3 5
1 -10 -4 5 5 2 3 -4
3 3 4 5 0 4 3 0
0 3 1 3 -5 1 -2 -3
-3 -9 -9 4 1 5 -1 -4
-7 -8 -7 -5 3 5 -5 1
-5 -2 -7 -8 -4 -1 3 -3
6 -6 1 8 -2 1 1 5
5 10 8 0 1 1 -4 -5
-8 6 7 3 2 -4 0 -5
8 7 6 4 4 1 -3 -1
-7 -1 8 -6 5 4 4 -3
8 4 -2 -8 -4 1 0 -2
-3 -3 -9 7 5 5 0 0
1 -5 -9 -4 5 -1 1 1
6 -4 -3 3 -4 4 -3 5
-1 7 -7 9 3 0 0 -5
0 -1 1 -2 -1 -5 1 -2
-1 9 -1 6 -5 5 2 3
1 -5 4 -10 -1 0 1 2
-2 -3 -10 -10 3 0 0 4
10 -9 7 -2 -1 -5 -2 5
-5 1 -7 -7 3 1 -4 -3
4 4 -3 -7 1 5 4 0
5 8 6 -8 4 3 -3 -2
-10 1 6 2 0 5 4 -3
-6 -10 -9 2 3 3 4 -2
-2 9 5 8 2 1 -1 -4
10 -5 -6 6 -4 4 -5 5
4 -7 -5 -10 1 2 -2 1
-4 -7 10 9 -1 -5 4 4
7 -9 4 -10 4 -5 3 1
-2 0 -10 -9 -2 4 -3 1
7 9 4 1 5 0 -3 5
1 3 -5 6 -2 -1 2 0
5 -8 -9 -7 -4 -4 -3 1
-10 5 -3 -8 -3 -5 4 -1
3 -3 7 8 1 2 5 0
-2 0 -3 -8 0 4 3 -1
-6 -4 0 8 2 0 -1 -5
2 10 3 8 -3 4 -2 -5
-4 -1 7 -5 4 -5 -2 5
-7 -5 -3 -5 -4 5 2 -3
-4 3 -8 4 4 5 3 5
9 -4 7 6 0 3 -5 4
-8 -5 10 -3 -2 -1 2 -4
2 0 -1 -5 -3 -2 -4 0
6 -6 -1 4 -3 3 0 2
9 6 -6 1 -1 -3 1 5
-3 7 4 -7 -4 2 5 -4
6 3 7 10 -1 1 3 3
3 -5 8 3 1 3 1 1
9 2 -6 -5 0 -1 -3 -4
-8 2 -9 -10 2 -4 5 -2
-7 -3 8 -6 -1 4 0 -4
0 -8 -9 -7 -4 3 0 -5
-8 8 3 5 5 0 4 5
-6 8 -1 7 -4 0 3 1
2 4 -5 2 -4 -4 2 0
2 4 -1 -7 -5 -1 3 0
-4 -2 -8 2 -2 -3 -5 -5
-4 7 7 8 -2 -5 4 2
6 8 5 7 0 0 -4 -1
6 -1 9 -9 -4 4 3 -3
-5 9 -1 -4 2 -1 -1 1
-8 9 -6 -5 -1 4 5 3
-4 -6 0 1 4 -2 1 1
0 4 4 -5 -4 -3 -4 4
-2 6 2 8 2 -5 -3 -2
-8 -3 6 -2 -1 3 -4 -5
-9 -7 5 0 -2 3 -5 3
7 -3 -3 9 3 -4 5 3
7 -7 0 -9 2 4 -3 -5
3 -2 -2 3 -2 1 -1 -2
-6 -2 2 7 -4 5 0 2
-5 3 -10 8 3 -4 -1 1
0 6 0 8 1 4 -1 -3
0 6 7 7 1 5 4 5
-6 5 -7 6 -2 -5 -3 4
-1 -5 -3 4 0 3 0 -1
-2 8 -5 -6 -3 1 2 -3
-5 -5 -1 -7 -5 3 1 -2
0 -8 -7 -10 -4 0 -5 5
6 8 -2 9 -3 -1 3 1
-2 2 3 5 -3 2 -3 -2
-2 -2 -9 10 0 -2 3 0
2 -6 6 -9 4 -1 1 -4
-5 10 -9 5 -2 1 -1 1
-6 -8 -4 3 -3 1 -4 -3
-8 10 5 7 3 2 3 -4
-3 4 5 -2 0 0 -1 -1
10 5 -8 -6 4 -1 2 0
2 -7 7 -2 1 5 -5 4
-1 -1 -3 -1 0 2 1 4
0 -5 -3 8 -1 4 -1 -4
3 6 3 5 1 1 0 -1
4 -5 -7 -1 -1 0 -1 -2
-3 -5 -8 0 -4 -3 2 0
-10 2 7 7 -5 3 -5 -4
-1 -7 6 -2 -1 5 3 4
10 -5 -1 -5 0 -5 -1 0
-7 -2 1 -8 2 5 -3 5
-6 -6 8 -7 3 5 -4 -3
-8 9 -8 9 -3 1 0 5
4 5 9 9 -1 3 -4 -2
4 -2 -10 -3 -1 0 4 5
-2 -4 5 2 2 3 0 1
-3 0 -3 -10 -4 4 1 3
3 -9 6 10 -4 4 2 4
6 7 4 6 5 -3 5 1
-7 5 -9 -9 0 0 -3 -3
4 -5 -3 3 -2 -2 0 -3
9 1 -2 -4 -4 4 -5 3
-9 6 -8 -1 -2 4 2 4
6 -8 -8 -2 4 0 5 5
10 -2 -9 -4 -3 1 0 2
-8 3 -7 -1 4 3 3 1
-2 -9 4 -1 3 -3 2 4
6 -6 -5 8 4 -1 0 -3
8 -10 -1 -5 4 -3 -5 -4
5 -3 2 8 -3 0 -3 4
10 2 4 3 -1 -3 0 -3
0 6 0 -10 -5 -1 0 -3
5 -9 0 -7 -3 -4 1 -1
3 -6 -8 -6 2 -5 3 5
-1 5 8 4 -1 -3 0 -1
-5 -2 8 3 3 5 -1 3
-10 9 8 8 5 -3 -3 3
-1 -6 -5 -1 -4 4 2 -2
6 10 -1 -9 -3 -2 1 5
-1 -7 8 -6 3 -1 -3 -4
-5 7 9 6 5 3 1 2
2 4 -1 4 0 0 5 -3
-10 -6 0 -8 -4 0 -4 -5
-8 8 -6 -3 -2 5 -3 3
9 0 -2 -8 -3 3 2 -5
-4 5 -6 10 3 1 -4 0
9 -2 -2 -7 -4 -1 -2 -1
3 -9 -10 -5 1 -3 -2 0
4 -9 0 -4 -4 0 3 1
-5 -9 -6 7 -5 3 -3 3
2 10 5 4 1 -4 1 -2
-3 9 -9 4 -3 -3 1 -2
4 -2 -6 -1 5 0 5 0
-4 -2 -9 9 0 -3 1 -1
-10 -7 -8 2 5 -4 5 -3
10 -4 -10 7 -2 -2 -5 -1
-3 7 7 -2 -3 2 -1 -4
9 -5 5 0 -4 0 -5 -3
-3 6 7 1 3 -2 -2 2
-3 -8 -3 -3 -3 0 -2 3
-5 3 9 1 3 -3 0 -4
7 -2 -7 2 -2 3 1 -3
-10 9 -7 6 -3 4 -3 0
10 -4 9 2 -2 5 4 -5
-10 2 -9 4 1 4 0 5
5 -1 -10 -10 -5 2 -4 -3
-3 -2 -4 -2 -5 -5 5 -3
1 10 -4 -9 3 -4 4 -3
3 -2 0 -8 4 -2 -1 -3
-10 1 1 -3 -1 3 5 3
3 2 -7 -9 4 -3 -2 -3
-6 4 7 10 0 -3 5 -4
5 -9 -8 1 0 4 -2 4
-1 -10 -8 8 -3 -1 -5 0
8 -6 -8 -9 3 -2 5 5
-5 2 0 -8 -2 -2 0 -5
-5 -1 10 0 -4 1 -1 4
-4 4 -6 -3 0 0 -5 -3
2 4 0 6 5 0 2 3
-10 -4 2 -8 2 0 -4 5
-8 0 3 9 -2 2 5 0
1 3 -2 -7 -5 2 3 -2
-4 0 0 -8 0 1 4 1
-3 7 0 -8 2 -1 1 -4
7 -3 4 -1 1 -5 -5 1
7 -4 -8 -8 -3 -2 -2 -5
8 6 1 9 -3 3 -1 -3
-9 2 8 0 4 -2 1 -4
-8 1 3 8 2 0 -4 -1
-4 -8 10 3 2 2 -3 2
8 -3 1 1 -4 0 -1 5
2 -5 3 -2 -5 -2 -3 1
2 -6 -3 -3 4 1 -4 -1
3 7 -8 0 1 -3 4 -2
1 9 7 8 -3 1 -1 -5
-4 -1 -1 -5 3 -5 -3 4
6 -2 6 10 1 5 2 3
-6 0 8 -7 4 -3 -4 0
-2 5 -7 -5 -2 5 1 -1
9 0 9 -4 2 2 5 -4
10 -1 -4 5 2 -4 -2 -5
10 -3 9 -9 3 4 -3 0
1 -5 4 -4 5 5 5 5
-10 4 9 10 3 0 2 2
6 9 1 9 5 -2 2 -4
-9 0 9 9 -2 2 -4 5
4 -2 -9 -9 -4 0 -4 4
3 -9 2 6 4 -3 5 -1
9 -10 -9 1 -5 4 0 -1
1 6 -10 -6 -3 3 -4 -2
-7 0 3 0 -5 4 -2 -5
3 7 9 -8 1 3 5 1
7 5 5 2 2 2 2 -4
-3 -2 9 0 3 0 -4 1
9 1 9 2 -2 -5 -1 3
-1 7 6 -8 3 5 -4 -2
-2 4 9 8 3 1 -1 5
-9 10 -5 6 -2 -3 -2 1
5 2 -3 6 4 -4 -5 3
3 4 6 5 0 0 2 0
0 0 -3 1 4 0 -5 4
-8 -3 0 5 2 3 2 1
7 -9 3 0 -5 0 2 3
6 -8 10 3 -1 2 1 -2
-6 -6 -4 -9 -3 -4 -2 5
7 1 7 2 3 5 -3 0
9 5 2 9 2 5 1 1
5 10 10 -2 -1 -1 3 -1
2 10 -7 9 1 -4 -2 -4
-5 -7 4 0 4 -2 -3 -1
3 4 -5 6 0 5 -1 -3
-8 -5 2 -7 4 5 -2 -2
-6 2 -3 -5 5 -5 -2 -4
4 3 -3 -5 1 -1 1 -4
9 -3 -2 -6 4 -2 0 0
6 4 -2 8 2 -4 -3 0
-7 7 -2 -4 -5 -3 0 -4
9 -10 -8 -4 0 5 0 -2
8 2 -8 -9 2 2 5 -4
6 -8 7 7 2 5 3 -3
3 5 -9 5 -1 3 -5 3
-1 1 9 10 4 -2 5 4
-2 5 -7 0 2 2 -3 1
-6 -1 6 -2 4 5 -4 0
-9 -6 -3 7 3 0 -2 -5
3 1 1 -4 -1 5 3 -1
-8 0 -6 1 -5 0 4 2
-3 5 -2 8 -1 4 3 2
6 -5 4 -9 1 3 1 -3
3 0 -2 -2 5 4 4 0
5 0 4 -8 4 4 -4 4
-3 10 -10 -6 -3 -4 1 4
-1 8 -7 8 -5 3 -4 -5
4 -1 2 8 1 -5 -3 5
2 1 2 -7 -4 3 5 -5
-9 -6 -3 3 2 -5 1 5
3 -1 8 -5 -1 2 2 -5
1 -7 2 1 -3 1 -1 2
2 -6 -10 -1 -3 1 5 5
4 -4 1 -5 0 3 5 5
7 -4 -10 -6 -2 -4 -1 0
4 -7 -3 10 0 3 -5 -3
-4 4 -8 5 -4 -1 0 4
1 10 5 0 -5 5 0 -5
-2 -5 2 -3 -1 5 -2 5
9 10 -6 -3 0 4 4 -5
-1 6 -5 -6 -1 -3 -4 1
10 5 -2 -4 -4 -5 2 -5
7 -3 0 10 3 -3 2 -2
-1 4 -9 10 -2 0 0 -1
7 2 2 9 1 4 2 4
10 -5 -6 8 -2 2 3 3
-5 -1 -4 -9 5 5 1 -2
-3 7 -3 0 -3 -1 -1 1
-2 -3 7 -8 -5 -1 3 5
3 -7 0 -6 -5 1 0 1
-3 -9 9 -6 -3 1 -3 4
5 -9 4 4 4 1 -5 0
-10 -3 1 -6 5 -1 -2 4
2 -6 4 3 0 -5 -5 -5
8 4 -5 1 4 -5 2 1
1 -10 5 3 -2 3 3 5
-4 -9 0 -4 1 -2 -2 -2
0 -6 -8 -6 -2 4 -1 -5
5 -4 5 -8 -4 -5 1 1
5 9 -5 9 -4 1 2 -5
10 8 -2 0 3 -1 2 4
-7 -5 5 -8 4 -2 4 -3
6 9 -10 8 3 1 -2 -5
6 -2 -3 -9 2 3 -4 5
-1 -9 -6 6 -3 0 -1 4
6 -6 -6 6 4 3 4 -5
-3 -2 -4 6 -5 5 5 0
10 -5 -7 -3 4 -2 2 5
8 -8 -8 -9 -4 1 -4 -2
1 5 -5 6 -1 -5 4 4
-3 10 -8 6 -5 -4 5 4
3 1 -2 9 -5 4 5 1
3 9 -5 2 -4 4 1 -1
-9 0 7 -2 5 -2 -4 -5
-5 -6 -7 2 3 5 1 1
-1 7 5 -9 5 5 4 0
-4 9 1 7 -2 -3 0 5
-7 5 -8 -4 3 4 3 -2
-1 -2 -9 4 -2 -1 -4 2
7 5 -6 0 -3 2 -3 1
2 -5 -8 2 -1 4 1 2
-1 0 8 -5 5 5 5 -1
5 0 10 6 5 3 4 4
7 3 2 -9 -5 1 -5 -4
-4 -8 -9 10 5 3 2 4
3 -2 -4 -5 1 -4 -4 1
4 -7 -10 -5 -1 3 -5 4
8 -10 -1 2 -1 4 -3 -5
4 -2 9 -2 -1 3 2 3
2 -9 7 3 -5 3 2 -4
6 7 6 -6 1 -3 -1 -2
-3 -6 10 3 2 -1 5 -3
7 1 -6 8 5 5 -5 -2
-10 -5 -9 10 3 -3 -2 5
-5 9 7 0 -5 -2 1 -5
10 -9 -7 0 -4 -3 3 2
7 0 -5 -4 2 -2 1 0
-8 6 3 -1 -3 -4 1 5
6 -8 -4 5 0 5 -1 3
9 9 -8 10 -5 3 1 3
7 -3 4 4 -1 4 2 0
-1 7 10 -6 -5 5 3 -1
7 6 -4 -2 2 0 0 -5
-3 7 3 -5 3 -2 2 1
5 -3 2 -7 2 1 0 4
8 2 6 -5 2 1 4 -1
5 9 4 -1 -5 -5 -3 3
10 0 -5 -3 2 3 2 -1
2 -1 -5 6 2 1 -1 -4
-9 -2 -6 -9 -2 -1 -1 -5
-9 10 4 0 4 -2 2 0
-5 7 5 9 4 1 -4 0
0 -6 -2 -8 3 1 -4 5
4 8 -6 8 3 0 -3 -3
-3 3 10 -6 -2 1 5 -2
4 -8 -7 -1 3 4 -4 2
-10 0 2 -5 -1 -4 -1 3
-9 9 8 4 -2 -4 4 3
0 3 -7 5 5 5 -2 0
-10 4 5 -4 2 0 -1 2
8 -6 8 -7 -1 0 -5 3
-2 -3 -6 3 5 -5 5 -2
-9 -8 3 -3 3 -2 -1 -3
-10 2 1 -3 -5 5 5 3
5 -9 -4 -2 4 2 0 1
10 9 -9 1 5 -2 1 -3
-7 5 0 4 0 -2 -3 -5
0 5 6 3 3 -4 -5 5
9 -8 3 9 -1 -3 -1 0
6 4 7 -2 2 5 -5 -2
0 -4 -6 7 2 3 3 3
-10 7 -10 -8 0 3 -3 3
0 4 5 -1 1 2 4 2
8 -3 10 -4 -4 2 -5 3
-10 -2 8 10 2 -5 -4 0
1 5 -6 -7 -5 -5 -4 -5
-9 8 -10 3 1 -3 -3 -4
-2 -2 2 -9 1 -4 -1 -4
10 -8 -6 1 3 -5 -4 2
10 9 -7 0 -3 -1 -3 5
-4 -6 2 -9 3 5 2 1
2 8 -7 8 3 -1 -4 3
-2 -7 -6 6 5 2 1 -5
-9 9 6 6 4 -2 -1 -3
9 -10 -9 -4 1 -2 -5 -4
-9 -8 -6 -1 1 4 -1 2
-1 -2 -2 5 -1 -4 0 1
10 -8 10 7 0 -3 -5 -2
5 -7 5 8 4 -5 -2 5
0 8 10 -9 -1 0 -3 -4
-4 7 -8 -1 3 -5 1 5
-1 2 2 10 5 3 0 5
9 10 7 8 -4 -4 -2 -4
3 6 5 -1 3 -2 -4 0
-1 7 8 3 -1 -1 5 -2
-9 7 -1 2 -5 0 -2 -4
3 9 -10 2 -2 1 5 4
8 -10 8 -10 -3 1 -3 0
9 1 -3 -6 2 4 -1 4
1 1 -1 -4 -3 -3 0 -2
-10 -5 -8 -9 -2 4 -5 -5
2 1 -7 0 4 -2 1 1
8 7 -9 8 -1 -1 0 -1
-4 7 -7 -9 -5 3 -5 -5
-1 1 2 -1 -5 0 3 3
-9 -7 -2 -2 3 4 3 4
9 8 6 0 -2 4 5 -1
-9 0 3 4 -2 2 3 -4
-3 6 8 -5 3 -2 0 -5
-1 6 5 0 -2 5 4 -4
4 3 5 -1 5 0 -1 -3
-8 7 -6 -1 -2 2 1 -2
4 5 -4 6 0 -3 -5 -4
-6 -1 9 -9 -2 0 -5 5
-2 5 6 2 -3 -4 -4 0
1 0 -9 -5 3 -1 4 -2
-9 1 1 -2 1 1 -4 2
-6 9 -4 2 -3 -3 2 2
10 -2 6 7 3 5 -5 -4
-3 -9 -5 7 3 5 4 4
0 -9 -4 10 5 2 1 1
-4 2 -1 10 -4 -3 2 2
3 -8 6 -5 -5 -3 1 -5
7 -3 -7 1 -3 0 -2 -1
7 0 5 -10 2 -4 5 3
8 6 8 -7 3 -2 -4 -3
3 9 7 5 0 2 -5 1
0 2 -2 2 2 -4 2 1
-10 -4 3 -8 3 3 5 0
8 5 5 -7 5 -3 4 -3
-10 -10 1 -1 5 1 0 0
-1 -1 -4 8 -5 -3 -3 3
-2 9 -6 -3 2 -3 2 3
7 6 -9 -1 0 -2 1 -1
1 -9 -1 9 -4 2 -4 4
-10 -9 -10 10 1 4 1 3
-9 -3 8 3 -3 3 4 -4
7 -4 -8 2 0 4 -5 4
10 10 -9 1 2 -1 2 -2
-7 2 3 5 1 1 0 -3
8 7 4 -9 -5 -3 0 -5
-6 0 3 1 -4 4 4 -5
-8 1 3 -3 -4 0 1 -5
8 7 9 0 5 -5 1 -2
1 -6 -2 -10 1 -3 -2 1
-2 8 -1 -9 1 3 0 1
-6 1 -3 -10 -4 3 3 -2
-5 -6 -3 1 -3 -2 -3 5
-3 -7 1 2 -3 0 -2 -1
5 -2 0 -5 -4 2 -1 -1
4 9 7 -9 1 2 -5 1
-1 -9 9 3 5 -2 -5 3
-10 -2 -6 -7 -2 5 -4 3
5 1 -7 0 2 -3 2 -4
-1 0 8 -6 -1 0 5 3
9 1 6 -10 3 1 -3 2
-4 4 -3 3 1 -3 -5 3
10 -6 7 2 1 4 1 4
10 6 5 -4 3 0 5 0
5 1 -7 -10 4 0 -5 -5
-1 -3 4 10 5 -3 5 1
9 0 4 -2 1 4 -2 3
-9 2 -7 3 4 -1 0 -3
4 2 -5 -2 1 -4 5 -1
3 3 2 -3 1 -5 4 0
1 -3 4 -1 -3 -2 -2 -1
-6 -9 2 -8 5 4 -4 -1

Thanks in advance.

[zobayer]

PLEASE FOLLOW FORUM RULES, DO NOT OPEN NEW THREAD WHILE THERE IS ALREADY ONE OPENED. USE EXISTING THREADS.

Here are my output for your input,

Code: Select all

F
T
T
F
F
F
F
F
F
F
F
T
F
F
F
F
F
T
F
F
F
F
F
T
F
F
T
F
F
F
F
T
T
F
F
F
F
T
F
T
T
T
F
T
T
F
F
F
F
T
T
F
T
T
F
T
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
F
T
F
T
F
F
T
F
T
F
F
T
F
F
F
T
F
F
F
T
F
F
F
T
F
T
T
T
F
F
T
F
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
T
F
T
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
T
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
F
F
T
F
T
F
F
T
F
T
F
F
F
F
F
T
F
F
F
F
F
F
F
F
F
F
F
F
F
T
F
T
T
F
F
F
F
F
F
T
F
F
F
T
T
T
F
F
F
T
T
F
T
F
T
F
F
F
F
F
F
F
F
T
T
F
F
F
F
F
T
F
T
F
F
F
F
F
F
T
F
F
F
F
F
F
F
F
T
F
F
F
F
F
F
T
T
F
F
T
T
F
F
F
F
T
F
T
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
T
T
F
F
F
F
T
T
F
F
F
F
F
T
T
F
F
F
F
F
T
F
T
F
F
F
T
T
F
F
T
T
T
F
F
F
T
F
F
F
F
F
F
T
F
T
F
F
F
T
F
T
F
T
F
F
F
T
F
F
F
F
T
F
F
F
F
T
F
F
T
F
T
T
T
F
F
F
F
F
F
T
F
F
F
F
T
F
F
F
F
F
F
F
T
F
T
F
T
T
F
F
F
F
T
T
F
F
F
F
F
F
F
F
F
F
T
F
T
F
F
F
F
F
F
F
F
F
F
F
F
T
F
F
F
F
T
T
F
F
F
F
T
F
F
F
T
F
F
T
F
T
F
F
T
F
F
F
F
T
F
F

[S.H.Bouwhuis]

Thanks for testing Zobayer!

Edit:
Oh man, that's annoying. I have the same thing.
There apparently is some special case I haven't considered.

If someone knows a special case, please tell us.

Here is my source code in case someone is interested.

Code: Select all

//
// 191_Intersection: Determine whether a line intersects a rectangle
//

#include <cstdio>
#define _CRT_RAND_S
#include <cstdlib>
#include <ctime>

// The base types
#ifdef WIN32
  typedef __int8            int8;
  typedef __int16           int16;
  typedef __int32           int32;
  typedef __int64           int64;
  typedef unsigned __int8   uint8;
  typedef unsigned __int16  uint16;
  typedef unsigned __int32  uint32;
  typedef unsigned __int64  uint64;
#else
  typedef char                    int8;
  typedef short                   int16;
  typedef long                    int32;
  typedef long long int           int64;
  typedef unsigned char           uint8;
  typedef unsigned short          uint16;
  typedef unsigned long           uint32;
  typedef unsigned long long int  uint64;
#endif

// These macros safely delete (an array of) objects
#define SAFE_DELETE(pObj)       { if(pObj) { delete pObj;   pObj = NULL; } }
#define SAFE_DELETE_ARRAY(pArr) { if(pArr) { delete[] pArr; pArr = NULL; } }

// Approximation functions for doubles
#define EPSILON   1e-10
int8 Dbl_Compare(double dA, double dB) { return (dA + EPSILON < dB ? -1 : (dA - EPSILON > dB ? 1 : 0)); }
#define Dbl_IsSmaller(dA, dB)      (Dbl_Compare(dA, dB) == -1)
#define Dbl_IsSmallerEqual(dA, dB) (Dbl_Compare(dA, dB) !=  1)
#define Dbl_IsEqual(dA, dB)        (Dbl_Compare(dA, dB) ==  0)
#define Dbl_IsBiggerEqual(dA, dB)  (Dbl_Compare(dA, dB) != -1)
#define Dbl_IsBigger(dA, dB)       (Dbl_Compare(dA, dB) ==  1)

  // The line types
enum LineType { point, horizontal, slope, vertical };

// The definition of a vertex
struct VERTEX
{
  double dX;
  double dY;
};

// A line of the form y = ax + b
struct LINE
{
  VERTEX   vertA;       // The starting point of the line
  VERTEX   vertB;       // The ending point of the line
  LineType type;        // The type of the line (point, horizontal, slope, vertical)
  double   dSlope;      // The slope (is the 'a'  in y = ax + b)
  double   dIntersect;  // The y-intersect (is the 'b'  in y = ax + b)
};

// The definition of a rectangle
struct RECTANGLE
{
  LINE lineLeft;    // The left side of the rectangle
  LINE lineTop;     // The top side of the rectangle
  LINE lineRight;   // The right side of the rectangle
  LINE lineBottom;  // The bottom side of the rectangle
};

// Function prototypes
                   bool GetIntersect_Line_Line(const LINE *pLineA, const LINE *pLineB, VERTEX *pVertInter);
                   void GetLineEquation(LINE *pLine);
                   bool IsEqualVertex(const VERTEX *pVertA, const VERTEX *pVertB);
template <class T> T    Max(T tA, T tB) { return tA > tB ? tA : tB; }
template <class T> T    Min(T tA, T tB) { return tA < tB ? tA : tB; }
template <class T> void Swap(T *ptA, T *ptB);
                   bool VertexInRectangle(const VERTEX *pVert, const RECTANGLE *pRect);
                   bool VertexOnLine(const VERTEX *pVert, const LINE *pLine);

// Uncomment the next line to generate random input
//#define GENERATE_RANDOM_INPUT


//---------------------------------------------------------------------------------------------
//                                      F U N C T I O N S
//---------------------------------------------------------------------------------------------


// This function is the entrance of the app
int main()
{
  // Should we generate random inputs?
#ifdef GENERATE_RANDOM_INPUT

  // Show the amount of inputs we're generating
  printf("500\n");

  // Generate the inputs
  for(int32 i32Input=0;i32Input<500;i32Input++)
  {
    uint32 u32Rand;

    // Line coordinates : range x and y = [-10, 10]
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 21) - 10);

    // Rectangle coordinates : range x and y = [-5, 5]
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 11) - 5);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 11) - 5);
    rand_s(&u32Rand);
    printf("%i ", int32(u32Rand % 11) - 5);
    rand_s(&u32Rand);
    printf("%i\n", int32(u32Rand % 11) - 5);
  }

#else

  int32 i32TotInputs;

  // Get the amount of lines we need to process
  if(scanf("%i", &i32TotInputs) == 1)
  {
    // Get the next input
    while(i32TotInputs-- > 0)
    {
      int32 i32Left, i32Top, i32Right, i32Bottom;

      // Get the intersecting line
      if(scanf("%i %i %i %i", &i32Left, &i32Top, &i32Right, &i32Bottom) == 4)
      {
        LINE line;

        // Initialize the intersecting line
        line.vertA.dX = i32Left;
        line.vertA.dY = i32Top;
        line.vertB.dX = i32Right;
        line.vertB.dY = i32Bottom;
        GetLineEquation(&line);

        // Get the intersecting rectangle
        if(scanf("%i %i %i %i", &i32Left, &i32Top, &i32Right, &i32Bottom) == 4)
        {
          RECTANGLE rect;

          // Fix the coordinates
          if(i32Right < i32Left)
            Swap(&i32Left, &i32Right);
          if(i32Top < i32Bottom)
            Swap(&i32Top, &i32Bottom);

          // Initialize the intersecting rectangle (left side)
          rect.lineLeft.vertA.dX = i32Left;
          rect.lineLeft.vertA.dY = i32Top;
          rect.lineLeft.vertB.dX = i32Left;
          rect.lineLeft.vertB.dY = i32Bottom;
          GetLineEquation(&rect.lineLeft);

          // Initialize the intersecting rectangle (top side)
          rect.lineTop.vertA.dX = i32Left;
          rect.lineTop.vertA.dY = i32Top;
          rect.lineTop.vertB.dX = i32Right;
          rect.lineTop.vertB.dY = i32Top;
          GetLineEquation(&rect.lineTop);

          // Initialize the intersecting rectangle (right side)
          rect.lineRight.vertA.dX = i32Right;
          rect.lineRight.vertA.dY = i32Top;
          rect.lineRight.vertB.dX = i32Right;
          rect.lineRight.vertB.dY = i32Bottom;
          GetLineEquation(&rect.lineRight);

          rect.lineBottom.vertA.dX = i32Left;
          rect.lineBottom.vertA.dY = i32Bottom;
          rect.lineBottom.vertB.dX = i32Right;
          rect.lineBottom.vertB.dY = i32Bottom;
          GetLineEquation(&rect.lineBottom);

          // Check whether either (or both) of the end points of the line resides on/within the rectangle
          if(VertexInRectangle(&line.vertA, &rect) || VertexInRectangle(&line.vertB, &rect))
            printf("T\n");
          else
          {
            VERTEX vertIntersect;

            // Both end points of the line are outside of the rectangle

            // Check whether the line intersects any of the rectangle's sides
            if(GetIntersect_Line_Line(&line, &rect.lineLeft,   &vertIntersect) ||
               GetIntersect_Line_Line(&line, &rect.lineTop,    &vertIntersect) ||
               GetIntersect_Line_Line(&line, &rect.lineRight,  &vertIntersect) ||
               GetIntersect_Line_Line(&line, &rect.lineBottom, &vertIntersect))
              printf("T\n");
            else
              printf("F\n");
          }
        }
      }
    }
  }

#endif

  return 0;
}


//---------------------------------------------------------------------------------------------


// This function determines whether 2 lines intersect (and where)
bool GetIntersect_Line_Line(const LINE *pLineA, const LINE *pLineB, VERTEX *pVertInter)
{
  bool bIntersecting = false;

  // Do we have parallel lines?
  if(pLineA->type == pLineB->type && Dbl_IsEqual(pLineA->dSlope, pLineB->dSlope))
  {
    // Are they overlapping or touching?
    if(VertexOnLine(&pLineA->vertA, pLineB) || VertexOnLine(&pLineA->vertB, pLineB)  ||  VertexOnLine(&pLineB->vertA, pLineA) || VertexOnLine(&pLineB->vertB, pLineA))
      bIntersecting = true;
  }
  else
  {
    // Do we have 1 vertical line?
    if(pLineA->type == vertical || pLineB->type == vertical)
    {
      const LINE *pLineSloped, *pLineVert;

      // Determine which line is vertical and which is sloped
      if(pLineA->type == vertical) { pLineSloped = pLineB; pLineVert = pLineA; }
      else                         { pLineSloped = pLineA; pLineVert = pLineB; }

      // Line sloped: y = ax + b, Line vertical: x = c

      // The intersection point is: (x,y) = (c, ac+b)
      pVertInter->dX = pLineVert->vertA.dX;
      pVertInter->dY = pLineSloped->dSlope * pLineVert->vertA.dX + pLineSloped->dIntersect;

      // Does the intersection point lie on line Sloped and on line Vertical?
      if(((Dbl_IsSmallerEqual(pLineSloped->vertA.dX, pVertInter->dX) && Dbl_IsBiggerEqual(pLineSloped->vertB.dX,  pVertInter->dX)) ||
          (Dbl_IsBiggerEqual(pLineSloped->vertA.dX,  pVertInter->dX) && Dbl_IsSmallerEqual(pLineSloped->vertB.dX, pVertInter->dX)))
        &&
         ((Dbl_IsSmallerEqual(pLineVert->vertA.dY, pVertInter->dY) && Dbl_IsBiggerEqual(pLineVert->vertB.dY,  pVertInter->dY)) ||
          (Dbl_IsBiggerEqual(pLineVert->vertA.dY,  pVertInter->dY) && Dbl_IsSmallerEqual(pLineVert->vertB.dY, pVertInter->dY))))
      {
        // The lines intersect
        bIntersecting = true;
      }
    }
    else
    {
      // Line A: y = ax + b, Line B: y = cx + d
      // ax+b = cx+d  =>  x = (d-b)/(a-c)

      // Are the lines not parallel?
      if(!Dbl_IsEqual(pLineA->dSlope, pLineB->dSlope))
      {
        // The intersection point is: (x,y) = ((d-b)/(a-c), a(d-b)/(a-c) + b)
        pVertInter->dX = (pLineB->dIntersect - pLineA->dIntersect) /
          (pLineA->dSlope - pLineB->dSlope);
        pVertInter->dY = ((pLineA->dSlope * (pLineB->dIntersect - pLineA->dIntersect) /
          (pLineA->dSlope - pLineB->dSlope))) +
          pLineA->dIntersect;

        // Does the intersecting point lie on line A and on line B?
        if(((Dbl_IsSmallerEqual(pLineA->vertA.dX, pVertInter->dX) && Dbl_IsBiggerEqual(pLineA->vertB.dX,  pVertInter->dX)) ||
            (Dbl_IsBiggerEqual(pLineA->vertA.dX,  pVertInter->dX) && Dbl_IsSmallerEqual(pLineA->vertB.dX, pVertInter->dX)))
          &&
           ((Dbl_IsSmallerEqual(pLineB->vertA.dX, pVertInter->dX) && Dbl_IsBiggerEqual(pLineB->vertB.dX,  pVertInter->dX)) ||
            (Dbl_IsBiggerEqual(pLineB->vertA.dX,  pVertInter->dX) && Dbl_IsSmallerEqual(pLineB->vertB.dX, pVertInter->dX))))
        {
          // The lines intersect
          bIntersecting = true;
        }
      }
    }
  }

  return bIntersecting;
}


//---------------------------------------------------------------------------------------------


// This function constructs the equation of the line going through the 2 vertices
void GetLineEquation(LINE *pLine)
{
  // y = ax + b
  // a = slope, b = y-intercept, VertA = (x1,y1), VertB = (x2,y2)
  //
  //     y2-y1     x2*y1-x1*y2
  // y = ----- x + -----------
  //     x2-x1        x2-x1

  // Do we have a horizontal line?
  if(Dbl_IsEqual(pLine->vertB.dY, pLine->vertA.dY))
  {
    // Do we have a line with 2 identical vertices?
    if(Dbl_IsEqual(pLine->vertB.dX, pLine->vertA.dX))
    {
      // We have a line consisting of exactly 1 point
      pLine->type       = point;
      pLine->dSlope     = 0.0;
      pLine->dIntersect = 0.0;
    }
    else
    {
      // We have an equation of the form y = b
      pLine->type       = horizontal;
      pLine->dSlope     = 0.0;
      pLine->dIntersect = pLine->vertA.dY;
    }
  }
  // Do we have a vertical line?
  else if(Dbl_IsEqual(pLine->vertB.dX, pLine->vertA.dX))
  {
    // We have an equation of the form x = c
    pLine->type       = vertical;
    pLine->dSlope     = 0.0;
    pLine->dIntersect = pLine->vertA.dX;
  }
  else
  {
    // We have an equation of the form y = ax + b
    pLine->type       = slope;
    pLine->dSlope     = (pLine->vertB.dY - pLine->vertA.dY) / (pLine->vertB.dX - pLine->vertA.dX);
    pLine->dIntersect = (pLine->vertB.dX * pLine->vertA.dY - pLine->vertA.dX * pLine->vertB.dY) / (pLine->vertB.dX - pLine->vertA.dX);
  }

#ifdef TEST
  PrintLineEquation(pLine);
#endif
}


//---------------------------------------------------------------------------------------------


// This function checks whether the 2 vertices are equal
bool IsEqualVertex(const VERTEX *pVertA, const VERTEX *pVertB)
{
  return Dbl_IsEqual(pVertA->dX, pVertB->dX) &&
         Dbl_IsEqual(pVertA->dY, pVertB->dY);
}


//---------------------------------------------------------------------------------------------


// This function swaps 2 elements around
template <class T> void Swap(T *ptA, T *ptB)
{
  T tTemp;

  // Swap the elements around
  tTemp = *ptA;
  *ptA  = *ptB;
  *ptB  = tTemp;
}


//---------------------------------------------------------------------------------------------


// This function determines whether the vertex lies on or within the rectangle
bool VertexInRectangle(const VERTEX *pVert, const RECTANGLE *pRect)
{
  return Dbl_IsBiggerEqual(pVert->dX, pRect->lineLeft.vertA.dX)    &&  Dbl_IsSmallerEqual(pVert->dX, pRect->lineRight.vertA.dX) &&
         Dbl_IsBiggerEqual(pVert->dY, pRect->lineBottom.vertA.dY)  &&  Dbl_IsSmallerEqual(pVert->dY, pRect->lineTop.vertA.dY);
}


//---------------------------------------------------------------------------------------------


// This function determines whether the vertex lies on the line
bool VertexOnLine(const VERTEX *pVert, const LINE *pLine)
{
  bool bVertexOnLine = false;

  // What type of line do we have?
  if(pLine->type == vertical)
  {
    // x = c

    // Does the vertex lie on the line?
    if(Dbl_IsEqual(pVert->dX, pLine->vertA.dX))
    {
      // Does the vertex lie on the line section?
      if(pVert->dY >= Min(pLine->vertA.dY, pLine->vertB.dY)  &&  pVert->dY <= Max(pLine->vertA.dY, pLine->vertB.dY))
        bVertexOnLine = true;
    }
  }
  else if(pLine->type == horizontal)
  {
    // y = b

    // Does the vertex lie on the line?
    if(Dbl_IsEqual(pVert->dY, pLine->vertA.dY))
    {
      // Does the vertex lie on the line section?
      if(pVert->dX >= Min(pLine->vertA.dX, pLine->vertB.dX)  &&  pVert->dX <= Max(pLine->vertA.dX, pLine->vertB.dX))
        bVertexOnLine = true;
    }
  }
  else if(pLine->type == point)
  {
    // Does the vertex lie on the line?
    if(IsEqualVertex(pVert, &pLine->vertA))
      bVertexOnLine = true;
  }
  else if(pLine->type == slope)
  {
    // Does the vertex lie on the line?
    if(Dbl_IsEqual(pVert->dY, pLine->dSlope * pVert->dX + pLine->dIntersect))
    {
      // Does the vertex lie on the line section?
      if(pVert->dX >= Min(pLine->vertA.dX, pLine->vertB.dX)  &&  pVert->dX <= Max(pLine->vertA.dX, pLine->vertB.dX))
        bVertexOnLine = true;
    }
  }

  return bVertexOnLine;
}