Comets have recently passed through your region of space, leaving behind a trail of dust. You would like to get a rough idea of the extent of this pollution, by finding the two most distant dust particles. Here, we define distance as the sum of differences between the x-, y-, and z-coordinates. For example, the distance between two particles at (1, 4, 9) and (4, 4, 4) is 3 + 0 + 5 = 8.
There are N comets, and we describe each comet with 11 numbers: (A, B, C), (D, E, F), (G, H, I), and (U, V). A comet’s position at time t is given by (At2 + Bt + C, Dt2 + Et + F, Gt2 + Ht + I). A comet leaves behind a particle of dust at every integer time t between U and V, inclusive.
For example, consider a comet described by (1, 0, 0), (0, −2, 1), (0, 0, 6), and (1, 5). It leaves behind 5 dust particles, at (1, −1, 6), (4, −3, 6), (9, −5, 6), (16, −7, 6), and (25, −9, 6). The first and last points are the most distant pair, with distance 24 + 8 + 0 = 32.
Pay close attention to the bounds. You may assume that there will be fewer than 100,000 dust particles, and that all positions will fit within a signed 32-bit integer.
- 1 ≤ N ≤ 100
- −500 ≤ A, D, G, U, V ≤ 500
- −100,000 ≤ B, C, E, F, H, I ≤ 100,000
- U ≤ V
The input file DATA5.txt will contain 5 test cases. Each will begin with a single integer N. N lines will follow, each containing 11 integers, in the order described above.
The output file OUT5.txt will contain 5 lines of output, one integer for each test case: the distance between the most distant pair of dust particles. There will be at least 2 dust particles.
1
1 0 0 0 -2 1 0 0 6 1 5
3
3 1 4 1 5 9 2 6 5 3 58
2 7 1 8 2 8 1 8 2 8 45
1 6 1 8 0 3 3 9 8 8 74
32
66726