Your code fails this IO:
Code: Select all
input:
1
4 9 11 2 1 1 7 5
output:
F
Moderator: Board moderators
Joseph Kurniawan wrote:Here's the sample inputAnd the Output will beCode: Select all
68 4 9 11 2 1 1 7 5 11 2 4 9 1 1 7 5 12 12 24 24 19 5 25 17 4 6 15 9 1 1 11 11 19 5 25 17 12 12 24 24 0 18 8 12 1 1 11 11 2 4 4 2 1 1 11 11 -4 9 -11 2 -1 1 -7 5 -11 2 -4 9 -1 1 -7 5 -12 12 -24 24 -19 5 -25 17 -4 6 -15 9 -1 1 -11 11 -19 5 -25 17 -12 12 -24 24 0 18 -8 12 -1 1 -11 11 -2 4 -4 2 -1 1 -11 11 4 -9 11 -2 1 -1 7 -5 11 -2 4 -9 1 -1 7 -5 12 -12 24 -24 19 -5 25 -17 4 -6 15 -9 1 -1 11 -11 19 -5 25 -17 12 -12 24 -24 0 -18 8 -12 1 -1 11 -11 2 -4 4 -2 1 -1 11 -11 -4 -9 -11 -2 -1 -1 -7 -5 -11 -2 -4 -9 -1 -1 -7 -5 -12 -12 -24 -24 -19 -5 -25 -17 -4 -6 -15 -9 -1 -1 -11 -11 -19 -5 -25 -17 -12 -12 -24 -24 0 -18 -8 -12 -1 -1 -11 -11 -2 -4 -4 -2 -1 -1 -11 -11 9 1 9 2 4 3 9 6 9 2 9 1 4 3 9 6 10 3 13 3 4 3 9 6 13 3 10 3 4 3 9 6 10 6 14 6 4 3 9 6 14 6 10 6 4 3 9 6 9 7 9 10 4 3 9 6 9 10 9 7 4 3 9 6 4 7 4 10 4 3 9 6 4 10 4 7 4 3 9 6 0 6 3 6 4 3 9 6 3 6 0 6 4 3 9 6 1 3 3 3 4 3 9 6 3 3 1 3 4 3 9 6 4 0 4 2 4 3 9 6 4 2 4 0 4 3 9 6 5 3 8 5 4 3 9 6 8 5 5 3 4 3 9 6 5 3 8 3 4 3 9 6 8 3 5 3 4 3 9 6 6 4 6 5 4 3 9 6 6 5 6 4 4 3 9 6 4 3 9 6 4 3 9 6 9 6 4 3 4 3 9 6 4 3 5 4 4 3 9 6 5 4 4 3 4 3 9 6 5 3 8 3 4 3 9 6 8 3 5 3 4 3 9 6 5 3 9 3 4 3 9 6 9 3 5 3 4 3 9 6 4 4 4 5 4 3 9 6 4 5 4 4 4 3 9 6 4 3 4 5 4 3 9 6 4 5 4 3 4 3 9 6 4 3 4 6 4 3 9 6 4 6 4 3 4 3 9 6 9 2 9 5 4 3 9 6 9 5 9 2 4 3 9 6 9 2 9 7 4 3 9 6 9 7 9 2 4 3 9 6
Code: Select all
F F F T T F T F F F T T F T F F F T T F T F F F T T F T F F F F F F F F F F F F F F F F T T T T T T T T T T T T T T T T T T T T T T T T
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
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
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;
}
Code: Select all
#include<stdio.h>
#define check_position(a,b) (a>=x1 && a<=x2 && (x3<=x4?(a>=x3 && a<=x4):(a>=x4 && a<=x3)) && b<=y1 && b>=y2 && (y3>=y4?(b<=y3 && b>=y4):(b<=y4 && b>=y3)))
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int test,a,b,c,x1,y1,x2,y2,x3,y3,x4,y4;double a1,a2,b1,b2,a3,a4,b3,b4;
for(scanf("%d",&test);test;test--)
{
scanf("%d %d %d %d %d %d %d %d",&x3,&y3,&x4,&y4,&x1,&y1,&x2,&y2);
a=y3-y4;
b=x4-x3;
c=x3*a+y3*b;
if(!a)
check_position(x1,y3) || check_position(x2,y3)?printf("T\n"):printf("F\n");
else if(!b)
check_position(x3,y1) || check_position(x3,y2)?printf("T\n"):printf("F\n");
else
{
a1=x1; b1=(double)(c-a*x1)/b;
a2=x2; b2=(double)(c-a*x2)/b;
a3=(double)(c-b*y1)/a; b3=y1;
a4=(double)(c-b*y2)/a; b4=y2;
check_position(a1,b1) || check_position(a2,b2) || check_position(a3,b3) || check_position(a4,b4)?printf("T\n"):printf("F\n");
}
}
return 0;
}