test 4
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

test 5
5
0 2 2 2 2
2 0 4 8 4
2 4 0 4 8
2 8 4 0 4
2 4 8 4 0

What is in test #35????? ;)

Edited by author 18.10.2011 01:30

It was enough 5 tests for me. In first algo I used double and couldn't
fly over test 5. Based on my fail on 5 test I remade algo radically, excluded doubles
and got Ac 0.078. So, 5 tests are enough for debugging.

Did you use __int64 or long arithmetic???

4
        0 550934784 999950884 449016100
550934784         0 449016100 999950884
999950884 449016100         0 550934784
449016100 999950884 550934784         0



Edited by author 19.10.2011 01:00

 If d=a^2+b^2 and d<=10^9=> a,b<=32000 that short int is enough.
Also brute force(main clue for integers) for solving triangle in int coordinates.

4
        0 550934784 999950884 449016100
550934784         0 449016100 999950884
999950884 449016100         0 550934784
449016100 999950884 550934784         0

0 0
0 23472
-21190 23472
-21190 0

Edited by author 21.10.2011 00:44

test 4
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

test 5
5
0 2 2 2 2
2 0 4 8 4
2 4 0 4 8
2 8 4 0 4
2 4 8 4 0

answers:

test 4
0 0
0 0
0 0
0 0
0 0

test 5
0 0
1 1
-1 1
-1 -1
1 -1

Edited by author 21.10.2011 00:44

@Vavan: What did you do between WA8 and WA35?
Thanks.

Edited by author 21.10.2011 19:56

if you have WA8, it will very likely caused by an invalid enumeration on brute force of triangle in whole numbers. for x**2+y**2 x = 0, y = floor(sqrt(D)) downto floor(sqrt(D / 2)) you should firstly to increase x, rather than y.

I'm not sure I understand what you mean.
Currently I enumerate the pairs (i, j) with

for (i = 0; i * i <= n; i++)
{
  j = (int) sqrtl(n - i * i);
  if (i <= j && j * j + i * i == n)
  {
    ... valid (i, j) pair...
  }
}

it shuld be faster

signed x = 0;
signed M = SQRT(D / 2);
for (signed y = SQRT(D); y >= M; y--) {
  unsigned Y = y * y;
  while (x * x + Y < D) {
    x++;
  }
  if (x * x + Y == D) {
    // valid (x, y)
  }
}

Edited by author 21.10.2011 23:43

Well I also do a loop from 1 to sqrt() but without the while so I don't think that's faster. Anyway not the speed is the problem.
I put a while(1); if some point exceeds 10^6 and if a D[i][j] value is incorrect so that a TLE should occur in these cases. I made a generator of tests and all looks OK. But WA #8...
Any suggestions, tricky tests?
Thanks

Edited by author 24.10.2011 19:57

I found my mistake. I was computing the first 3 points then thought the rest of them are uniquely determined. But this is false, for example if the first N-2 points are collinear, than the N-1 one could be, by symmetry, on two locations. By ignoring one of those solutions for N-1, the N-th point may not be determined and assume the current input is impossible to solve.
Now I did a sort of backtracking with all solutions for each point but obviously got TLE 39. So work in progress :)

PS: I've read in some other topic about writing the sqrt in assembly but I don't think that's the way of solving this problem :)

Edited by author 24.10.2011 23:30

AC, woo-hoo!
Indeed, if the points 0..i-1 are fixed and collinear, the solution for the rest of the points is not unique because we have an axis of symmetry. Otherwise, if at least 3 points are non-collinear, the solution is unique.

Edited by author 27.10.2011 21:09

I got wa32 and fixed to the test:
5
 0  4 36  5  2
 4  0 16  5  2
36 16  0 29 26
 5  5 29  0  9
 2  2 26  9  0

0 0
0 2
0 6
2 1
-1 1

and more:
5
0 4 25 16 100
4 0 9 36 64
25 9 0 81 25
16 36 81 0 196
100 64 25 196 0

0 0
0 2
0 5
0 -4
0 10

Edited by author 01.05.2016 01:52