Statistics

Problem Statement

The problem statement contains an image.

In VLSI design it's important to connect certain pairs of points on a circuit using as little wire as possible. Given an empty circuit board of size N x N, we want to connect the two points A₁ and A₂ with each other using one wire, and the two points B₁ and B₂ with each other using another wire. The wires must go along the horizontal and vertical edges on the grid (see figure), and the two wires may not share a common vertex.

Create a class ConnectingPoints containing the method shortestWires, which takes an int N, the number of vertices on one side of the circuit board, and a pair of int[], X and Y, each containing four elements. Elements 0 and 1 in X and Y contain the coordinates for A₁ and A₂, and elements 2 and 3 in X and Y contain the coordinates for B₁ and B₂. The method should return the minimum length of wires needed to connect A₁ with A₂ and B₁ with B₂. If it's not possible to connect the points, return -1 (see example 1).

Definition

Class:

ConnectingPoints

Method:

shortestWires

Parameters:

int, int[], int[]

Returns:

int

Method signature:

int shortestWires(int N, int[] X, int[] Y)

(be sure your method is public)

Constraints

• N will be between 2 and 500, inclusive.
• X and Y will each contain exactly four elements.
• Each element in X and Y will be between 0 and N-1, inclusive.
• All four coordinate pairs described by X and Y will be distinct.

Examples

1. 7

   {2,5,4,4}

   {1,4,5,0}

   Returns: 15

   This is the example in the problem statement.

2. 100

   {0,99,0,99}

   {0,99,99,0}

   Returns: -1

   The points to be connected are on the opposite corners of the circuit board, and there is no way to connect them with each other without crossing wires. Hence the method returns -1.

3. 500

   {250,251,2,495}

   {273,273,273,273}

   Returns: 496

4. 10

   {0,8,0,8}

   {0,9,9,0}

   Returns: -1

5. 10

   {0,8,0,8}

   {0,8,8,0}

   Returns: 36

6. 100

   {50,51,50,51}

   {50,51,51,50}

   Returns: -1

7. 100

   {49,51,49,51}

   {49,51,51,49}

   Returns: 12

8. 500

   {1,499,1,499}

   {1,499,499,1}

   Returns: 1996

9. 13

   {5,5,5,5}

   {3,7,6,11}

   Returns: 13

10. 500

    {0,1,499,499}

    {0,0,498,499}

    Returns: 2

11. 100

    {32,75,49,7}

    {50,50,50,50}

    Returns: 89

12. 98

    {32,75,49,7}

    {97,97,97,97}

    Returns: -1

13. 500

    {0,473,0,7}

    {499,237,495,499}

    Returns: 2198

14. 10

    {0,8,0,7}

    {9,1,7,9}

    Returns: 43

15. 100

    {50,50,50,50}

    {32,75,49,7}

    Returns: 89

16. 96

    {95,95,95,95}

    {32,75,49,7}

    Returns: -1

17. 500

    {499,1,497,499}

    {499,1,499,497}

    Returns: 2988

18. 11

    {1,8,3,2}

    {0,7,0,1}

    Returns: 16

19. 6

    {5,0,0,3}

    {5,1,4,4}

    Returns: 12

20. 10

    {9,4,7,5}

    {4,4,2,8}

    Returns: 17

21. 14

    {6,13,1,8}

    {5,9,10,9}

    Returns: 19

22. 11

    {5,0,0,10}

    {2,8,6,7}

    Returns: 32

23. 5

    {3,2,0,3}

    {3,3,3,0}

    Returns: 7

24. 5

    {2,3,4,3}

    {2,1,4,2}

    Returns: 5

25. 13

    {5,12,0,11}

    {0,9,11,4}

    Returns: 34

26. 7

    {2,1,4,4}

    {4,2,2,5}

    Returns: 6

27. 10

    {9,4,5,8}

    {5,8,3,3}

    Returns: 11

28. 11

    {3,9,10,7}

    {6,8,6,1}

    Returns: 16

29. 14

    {2,0,2,10}

    {1,1,13,6}

    Returns: 17

30. 14

    {13,8,1,9}

    {12,1,8,2}

    Returns: 30

31. 6

    {1,4,0,2}

    {2,5,1,3}

    Returns: 10

32. 14

    {2,1,6,8}

    {7,9,3,8}

    Returns: 10

33. 7

    {3,4,0,6}

    {1,4,1,6}

    Returns: 15

34. 12

    {7,10,2,7}

    {4,5,5,10}

    Returns: 14

35. 9

    {2,0,8,2}

    {7,8,2,4}

    Returns: 11

36. 10

    {1,1,5,1}

    {3,9,8,7}

    Returns: 13

37. 9

    {6,1,2,4}

    {1,0,2,2}

    Returns: 8

38. 10

    {8,7,0,3}

    {4,7,7,1}

    Returns: 13

39. 13

    {10,4,5,2}

    {10,6,10,4}

    Returns: 19

40. 7

    {3,5,4,3}

    {4,3,0,5}

    Returns: 11

41. 7

    {1,0,2,0}

    {2,5,0,4}

    Returns: 10

42. 14

    {10,10,6,6}

    {12,5,5,1}

    Returns: 11

43. 308

    {295,22,208,137}

    {32,293,155,270}

    Returns: 720

44. 172

    {15,39,155,116}

    {96,52,161,99}

    Returns: 169

45. 192

    {155,101,32,87}

    {102,51,116,159}

    Returns: 203

46. 439

    {158,275,80,176}

    {27,94,272,310}

    Returns: 318

47. 108

    {78,61,17,19}

    {101,33,90,100}

    Returns: 97

48. 279

    {13,186,116,110}

    {204,78,270,58}

    Returns: 559

49. 373

    {17,233,139,86}

    {341,23,228,113}

    Returns: 702

50. 251

    {102,23,69,4}

    {24,119,140,192}

    Returns: 291

51. 179

    {156,122,154,41}

    {11,102,160,130}

    Returns: 268

52. 130

    {47,41,30,69}

    {42,105,116,125}

    Returns: 117

53. 273

    {23,255,129,128}

    {140,153,8,213}

    Returns: 573

54. 195

    {9,81,144,73}

    {54,15,43,103}

    Returns: 242

55. 316

    {18,207,286,149}

    {178,255,46,53}

    Returns: 410

56. 5

    {2,3,2,3}

    {2,3,3,1}

    Returns: 7

57. 5

    {2,4,4,3}

    {3,0,2,0}

    Returns: 16

58. 5

    {4,2,3,4}

    {0,3,0,2}

    Returns: 16

59. 5

    {2,2,2,2}

    {2,4,3,1}

    Returns: 8

60. 6

    {5,2,1,5}

    {3,0,4,0}

    Returns: 22

61. 6

    {2,5,5,1}

    {0,3,0,4}

    Returns: 22