Statistics

Problem Statement for "CableWoes"

Problem Statement

The problem statement contains an image.

More and more electronic devices can be connected to the internet. So far, most of them don't support wireless networking, which means you have to pull TP (twisted pair) cables in your apartment. You also have to use hubs, which split a cable from one connection to four other connections. A connection can either be the internet connection, an electronic device or a hub. All cables must be pulled on the floor along the walls, and all connections will be at the floor near a wall. There will be a single internet connection in the apartment, and all electronic devices (there will always be more than one) must be connected to it through one or more hubs. The hubs may be interconnected as well.

Given the design of an apartment as a top-down view, the number of hubs at your disposal, the location of the internet connection and the locations of all electronic devices, determine the least amount of TP cable needed. You may place the hubs anywhere along a wall. Several hubs can be placed at the exact same location, and hubs can be at the same location as other existing connections.

Consider the image below, showing the design of an apartment from a top-down view. The red dot marks the internet connection, the green dots mark electronic devices, the gray boxes the positions of the hubs, and the blue lines TP cable. Note that the dots, boxes and lines are slightly separated from the wall on the image, but this is for clarification only.

The apartment design will be given as a String[] describing the top-down view as a simple polygon. All lines in the polgyon will be either horizontal or vertical. Each element will be in the form "<x> <y>" describing a point in the polygon. The points will be given in either clockwise or counter-clockwise order.

The connections will also be given as a String[], where each element will be in the format "<x> <y>". The first element will be the location of the internet connection, and the other elements the locations of the electronic devices.

Create a class CableWoes containing the method leastTPCable which takes a String[] design, the apartment design, a String[] connections, the locations of the connections, and an int hubs, the number of hubs at your disposal. The method should return an int, the least amount of TP cable needed to be pulled. If it's not possible to connect all devices to the internet, return -1 (see example 4).

Definition

Class:
CableWoes
Method:
leastTPCable
Parameters:
String[], String[], int
Returns:
int
Method signature:
int leastTPCable(String[] design, String[] connections, int hubs)
(be sure your method is public)

Notes

  • Not all hubs at your disposal need to be used, see example 3.
  • The coordinates in connections are not necessarily unique, see example 2.

Constraints

  • design will contain between 4 and 50 elements, inclusive.
  • connections will contain between 3 and 50 elements, inclusive.
  • Each element in design and connections will be in the format " ".
  • The elements in design will be unique.
  • design will describe a simple polygon containing only horizontal and vertical lines. No lines in the polygon will intersect or overlap other lines.
  • All coordinates in connections will be on a line in the polygon describing the apartment.
  • Each and in design and connections will be an integer between 0 and 1000, inclusive, and will not contain any leading zeros.
  • hubs will be between 1 and 20, inclusive.

Examples

  1. {"1 1","6 1","6 5","7 5","7 1","12 1","12 5","8 5", "8 6","10 6","10 8","8 8","8 9","10 9","10 11", "6 11","6 7","5 7","5 11","1 11","1 6","5 6","5 5","1 5"}

    {"4 6","1 4","3 1","11 1","10 10","2 11"}

    2

    Returns: 66

    This is the example in the picture. Hubs have been placed at "1 4" and "2 11".

  2. {"1 1","6 1","6 5","7 5","7 1","12 1","12 5","8 5", "8 6","10 6","10 8","8 8","8 9","10 9","10 11", "6 11","6 7","5 7","5 11","1 11","1 6","5 6","5 5","1 5"}

    {"4 6","1 4","3 1","11 1","10 10","2 11"}

    3

    Returns: 59

    Same as above, except that we now have three hubs at our disposal. Even though we don't need three hubs, using them all decreases the cable length a bit. The hubs should be placed at "1 4", "2 11" and "4 6".

  3. {"0 0","1 0","1 1000","0 1000"}

    {"0 500","1 500","0 500","1 500"}

    1

    Returns: 2002

    No matter where the hub is placed along the wall, the same amount of cable is needed. Note that the distance between "0 500" and "1 500" is 1001 and not 1, since the cable must go around the whole wall.

  4. {"0 0","0 10","10 10","10 0"}

    {"0 0","0 10","10 10","10 0","0 0","0 10","10 10","10 0"}

    15

    Returns: 30

    Only 4 of the 15 hubs are needed to get the optimal solution.

  5. {"0 0","0 10","10 10","10 0"}

    {"5 0","5 0","5 0","5 0","5 0","5 0","5 0"}

    1

    Returns: -1

  6. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90", "240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150", "110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220", "120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320", "250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"40 359","40 360","40 360","40 358","40 360","40 360","40 360","40 360","40 360","40 357","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360","40 360"}

    20

    Returns: 3

  7. {"1 0","1 1","0 1","0 0"}

    {"1 1","0 1","1 0","0 1","1 1","0 0","1 0","1 1","0 1","1 0","1 1","0 0","0 0","1 0","0 1","1 1","0 1","1 0","0 1","1 1","0 0","1 0","1 1","0 1","1 0","1 1","0 0","0 0","1 0","0 1","1 1","0 1","1 0","0 1","1 1","0 0","1 0","1 1","0 1","1 0","1 1","0 0","0 0","1 0","0 1","1 1","0 1","1 0","0 1","1 1"}

    17

    Returns: 3

  8. {"1 0","1 1","0 1","0 0"}

    {"1 1","0 1","1 0","0 1","1 1","0 0","1 0","1 1","0 1","1 0","1 1","0 0","0 0","1 0","0 1","1 1","0 1","1 0","0 1","1 1","0 0","1 0","1 1","0 1","1 0","1 1","0 0","0 0","1 0","0 1","1 1","0 1","1 0","0 1","1 1","0 0","1 0","1 1","0 1","1 0","1 1","0 0","0 0","1 0","0 1","1 1","0 1","1 0","0 1","1 1"}

    16

    Returns: 4

  9. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"40 150","362 70","40 334","288 40","40 209","70 161","40 124","371 40","171 80","240 44","260 139","70 304","260 65","90 169","330 250","154 80","260 65","240 158","339 70","290 70","70 90","142 120","170 139","70 329","360 279","70 74","160 300","181 40","260 87","150 329","40 113","164 370","300 320","182 40","212 370","129 220","247 240","187 80","200 280","219 180","260 95","323 40","40 231"}

    16

    Returns: 4402

  10. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"473 0","1000 341","0 976","690 1000","174 0","0 306","1000 21","777 0","0 14","449 1000","446 0","229 0","450 0","545 1000"}

    7

    Returns: 3397

  11. {"0 1000","1000 1000","1000 0","0 0"}

    {"0 130","782 0","735 1000","1000 34","1000 553","41 1000","0 260"}

    4

    Returns: 3418

  12. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"300 281","171 180","120 225","360 291","360 236","183 370","200 274","192 190","40 245","240 96","70 80","70 134","239 300","250 326","154 220","290 219","156 190","150 80","184 80","240 66","360 241","290 100","221 300","180 220","240 106","70 131","290 96","120 174","330 263","142 190","113 40","250 360","70 98","70 84","290 223","181 370","153 190","240 167","130 88","228 90","76 40"}

    13

    Returns: 4527

  13. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"185 1000","1000 195","782 1000","1000 476","0 861","1000 299","514 1000","1000 317","0 214"}

    4

    Returns: 3036

  14. {"0 1000","1000 1000","1000 0","0 0"}

    {"985 1000","1000 969","138 0","38 0"}

    1

    Returns: 3808

  15. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"165 80","270 320","240 78","326 320","237 180","223 370","151 180","171 190"}

    2

    Returns: 3369

  16. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"1000 576","0 475","118 0","154 1000","1000 672","929 0","1000 880","128 1000","836 1000","525 1000","0 423","0 387","915 0","21 1000","0 273","716 1000","0 272","2 0","658 0","73 0","792 0","1000 462","1000 498","312 0"}

    9

    Returns: 4547

  17. {"0 1000","1000 1000","1000 0","0 0"}

    {"526 1000","90 0","1000 50","679 0","0 574","0 312","220 0","0 963","0 242","717 0","1000 43","1000 84","120 1000","0 889","909 0","441 0","0 235","1000 550","847 0","0 301","1000 573","1000 436"}

    7

    Returns: 4736

  18. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"319 40","381 70","108 40","40 118","240 96","70 160","254 320","386 40","265 320","143 300","138 150","170 93","160 100","154 150","173 80","360 216","103 120","105 150","200 296","261 320","90 172","110 176","90 184","300 272","195 240","390 62","102 300","297 40","254 300","330 255","172 40","120 251"}

    11

    Returns: 4400

  19. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"0 246","172 1000","668 1000","417 1000","281 1000","1000 445","524 0","438 1000","1000 291","427 1000","0 80","467 1000","0 3","130 0","804 0","251 1000","0 432","297 0","1000 174"}

    4

    Returns: -1

  20. {"0 1000","1000 1000","1000 0","0 0"}

    {"1000 225","1000 596","859 1000","896 0","424 0","634 0","739 0"}

    2

    Returns: 2350

  21. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"40 251","374 70","154 300","387 40","240 178","360 300","297 40","40 133","240 54","360 315","300 272","133 80","70 170","218 90","110 160","207 240","171 370","240 148","240 99","240 106","40 185","214 180","338 40","330 70","247 240"}

    8

    Returns: 4721

  22. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"383 1000","0 392","622 0","1000 859"}

    1

    Returns: 3744

  23. {"0 1000","1000 1000","1000 0","0 0"}

    {"0 931","170 1000","391 0","0 629","690 1000","702 1000","331 0","1000 430","574 0","0 711","1000 936","664 1000","1000 701","787 1000","0 280","421 0","476 1000","959 1000","351 0","1000 819","0 947","1000 676","866 1000","117 1000","566 0","1000 596","0 624","903 1000","616 1000","1000 753","0 979","1000 384","812 0","0 420"}

    10

    Returns: -1

  24. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"147 190","174 190","49 360","292 320","238 40","140 180","290 143","40 111","249 370","40 122","125 150","120 153","62 100","357 320","149 150","124 40","332 40","70 91","40 315","58 360","75 300","40 284","191 270","53 100","330 228","193 240","70 316","70 153","40 182","281 320","330 244","70 91","330 246","148 270","170 134","110 158","240 42","224 40","40 265","82 200","229 300"}

    13

    Returns: 4632

  25. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"0 77","1000 993","583 1000","359 0","1000 562","1000 472","1000 395","1000 550","712 0","833 1000","1000 852","1000 580","383 1000","0 984","106 1000","0 593","1000 373","0 719","1000 362","822 0","106 1000","913 0","0 322","0 572","1000 400","0 402","788 0","536 1000","537 1000","271 0"}

    10

    Returns: 5277

  26. {"0 1000","1000 1000","1000 0","0 0"}

    {"0 730","0 714","684 1000","1000 154","1000 768","507 0","807 1000","1000 624","1000 537","773 1000","1000 446","1000 94","943 0","187 1000","359 1000","91 1000","464 0","870 0","0 225","1000 471","0 645","296 1000"}

    7

    Returns: 5067

  27. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"40 264","286 320","40 120","360 285","176 270","228 90","234 370","120 174","190 236","152 300","139 40","330 225","260 144","188 180","169 220","250 348","158 80","290 147","373 40","108 150","178 80","260 179","70 150","237 240","186 180","148 150","196 80","191 370","40 150","228 40","70 89","116 40","146 40","197 270","122 190","359 40","360 216","378 70","70 80","260 89","240 117","290 186","140 270","40 239","390 69"}

    17

    Returns: 4398

  28. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"878 0","0 625","894 1000","1000 510","54 0","0 230","647 0","303 0","0 589","0 322"}

    5

    Returns: 3303

  29. {"0 1000","1000 1000","1000 0","0 0"}

    {"1000 329","0 470","0 149","536 0","1000 396","0 311","0 243","622 1000","0 421","1000 644","249 1000","0 668","630 1000","0 367","815 1000","1000 847","900 0","179 0","1000 711","1000 260","1000 654","294 0","0 27","0 41","480 1000","810 0","321 0","0 432","1000 973","303 0","23 1000","1000 990","1000 307","1000 734","0 257","809 1000","0 38","0 92","0 603","1000 687","96 0","0 67"}

    12

    Returns: -1

  30. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"120 264","40 143","245 300","155 300","222 80","120 120","170 270","182 270","150 320","170 304","250 362","244 370","200 293","130 93","161 370"}

    8

    Returns: 2378

  31. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"929 0","604 0","0 988","0 138","785 0","0 633","877 0","205 0","124 0","1000 441","860 0","1000 527","489 1000","414 1000","398 0","0 908","232 0","801 0","41 0","0 775","0 415","508 1000","391 0","0 368","652 1000","230 1000","0 100","439 0","1000 455","0 189","316 1000","806 1000","0 539","1000 472","630 0","1000 424","0 540","279 0","2 1000","1000 793","191 1000","178 0","1000 158","366 0","0 293","776 1000","0 139","1000 770","829 0","141 0"}

    16

    Returns: 5701

  32. {"0 1000","1000 1000","1000 0","0 0"}

    {"937 1000","194 1000","0 267","498 0","17 1000","539 1000","0 956","561 0","0 235","0 837","303 1000","164 1000","518 0","649 1000","1000 692","1000 771","1000 752","1000 414","1000 32","1000 163","1000 773","95 1000","1000 955","858 1000","380 0"}

    8

    Returns: 5061

  33. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"330 183","159 270","360 255","70 194","240 144","170 122","110 173","360 272","240 61","70 82","107 120","70 52","110 183","328 40","260 116","360 229","360 187","230 240","274 240","153 100","240 131","330 185","211 300","154 300","247 300","222 80","330 223","70 49","360 290","40 290","384 70","188 370","136 40","147 220","224 300","58 100","73 300","40 192"}

    15

    Returns: 4374

  34. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"1000 49","0 523","1000 347","0 713","0 752","1000 878","348 0","786 1000","658 1000","555 1000","534 1000","343 0","202 0","0 357","0 677","125 0","0 764","304 1000","228 0","1000 3","0 669","726 1000","1000 390","1000 260","1000 447"}

    8

    Returns: 4832

  35. {"0 1000","1000 1000","1000 0","0 0"}

    {"550 1000","0 755","1000 477","623 0","0 117","178 1000","322 1000","1000 63","417 1000","191 1000","924 1000","418 1000","1000 341","0 286","1000 914","402 1000","1000 97","1000 823","1000 48","250 1000","438 0","811 1000","216 1000","47 0","414 0","0 614","1000 40","24 0","0 10","1000 443","616 0","13 1000","501 0","118 0","61 0","637 0","131 0","889 0","1000 372","0 68","330 1000","678 1000","137 1000","0 241","0 617","453 1000","425 1000"}

    17

    Returns: 5019

  36. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"351 320","260 130","101 150","196 240","292 40","113 300"}

    2

    Returns: 2570

  37. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"1000 58","0 946","1000 886","445 0","670 1000","106 1000","1000 172"}

    2

    Returns: 3731

  38. {"0 1000","1000 1000","1000 0","0 0"}

    {"0 713","0 458","1000 370","105 0","657 1000","0 153","1000 969","566 0","160 1000","1000 847","0 868","254 1000","569 1000","0 993","628 1000","904 0","522 1000","264 1000","765 1000","907 1000","853 0","682 1000","1000 688","1000 778","1000 402","0 542","939 0","341 1000","602 0","0 457","0 214","0 365","68 0","0 293","1000 81","0 531","0 595","0 609","37 0","0 66","1000 514","0 354","1000 528"}

    15

    Returns: 5252

  39. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"273 240","222 370","154 120","40 335","187 370","42 100","260 60","130 98","179 90","70 141","40 255","187 190"}

    4

    Returns: 3703

  40. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"1000 238","612 0","602 0","574 1000","1000 933","1000 735","527 0","874 0","1000 497","0 291","400 1000","0 542","61 0","0 108","496 0","246 1000","1000 276","990 0","230 1000","317 1000","479 0","0 614","0 55","1000 89","1000 180","1000 919","784 1000","485 0","0 479","627 1000","0 6","827 1000","509 0","0 451","490 0","706 1000","1000 400","0 355","362 0","104 0","726 0","967 0"}

    14

    Returns: 5120

  41. {"0 1000","1000 1000","1000 0","0 0"}

    {"0 425","615 1000","348 1000","1000 383","1000 508","0 625","930 1000","0 656","0 549","666 0","1000 950","1000 292"}

    4

    Returns: 3619

  42. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"192 180","70 41","74 120","90 153","113 120"}

    1

    Returns: 1306

  43. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"0 761","334 0","679 1000","0 173","686 1000","0 450","1000 768","180 0","280 0","0 436","0 829","31 0","0 358","384 0","0 439","0 620","73 1000","669 0","973 1000","455 0","1000 648","1000 722","752 1000","0 479","1000 587","581 0","1000 519","402 0","1000 86","446 1000","709 0","460 1000","1000 673","629 1000","44 1000","73 1000","989 0","0 664","894 1000","1000 501","0 38","567 0","179 1000","0 718","1000 250","1000 686"}

    14

    Returns: -1

  44. {"0 1000","1000 1000","1000 0","0 0"}

    {"1000 176","1000 24","1000 469","1000 485","835 0","1000 728","431 0","263 0","1000 396","548 0","0 385","239 0","0 533","1000 221","223 0","351 0","0 861","867 0","750 0","0 197","0 780","1000 178","0 491","1000 551","292 0","0 439","249 1000","162 0","1000 496","509 0","855 1000","785 0","0 721","0 919","0 744","436 0","0 316","0 110","774 0","0 26","185 1000","296 0","596 1000","0 23","813 0"}

    15

    Returns: 5271

  45. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"360 222","240 142","121 300","55 100","70 141","330 195","70 72","382 70","40 325","299 320","300 286","116 190","276 40","84 300","150 366","169 80","138 100","40 240","240 153","151 180","240 108","260 149","240 114","90 157","127 40","40 113"}

    9

    Returns: 4036

  46. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"382 0","600 1000","561 1000","1000 106","41 1000","1000 810","0 969","859 1000","1000 606","1000 320","989 0","1000 500","453 0","0 889","860 1000","0 139","787 0","38 0","0 413","0 255","292 1000","1000 572","1000 806","1000 682","169 0","1000 779","1000 769","352 0","123 1000","733 0","983 1000","572 0","830 0"}

    11

    Returns: 5365

  47. {"0 1000","1000 1000","1000 0","0 0"}

    {"121 0","619 1000","794 0","0 588","450 0","0 732","261 0","0 761","0 110","613 0","0 707","916 0","201 0","582 0","746 0","0 739","101 1000","1000 181","902 1000","0 367","128 1000","41 1000","549 1000","1000 525","0 270","135 0","609 1000","1000 304","0 283","88 0","878 0"}

    11

    Returns: 4534

  48. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"236 90","150 328","305 40","40 297","70 347","294 300","70 136","300 272","218 80","56 360","290 225","250 300"}

    3

    Returns: -1

  49. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"906 1000","0 631","535 0","401 0","65 1000","1000 135","1000 605","1000 698","841 1000","0 899"}

    3

    Returns: 4559

  50. {"0 1000","1000 1000","1000 0","0 0"}

    {"1000 403","318 1000","0 770","1000 51","0 904","425 1000","600 0","442 1000","276 1000","385 0","0 709","1000 69","0 14","0 386","476 1000","296 1000","149 0"}

    7

    Returns: 3529

  51. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"240 112","143 270","360 315","70 334","360 286","70 128","355 70","290 77","260 69","170 305","138 80","120 161","226 40","40 114","70 147","191 90","353 70","40 143","136 300","70 130","70 62","120 120","290 240","370 70","239 180"}

    6

    Returns: -1

  52. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"267 1000","244 0","0 623","879 1000","0 85","1000 457","0 240","0 452","299 0","254 0","1000 431","0 639","0 800","1000 850","1000 746","1000 813","466 1000","42 1000","1000 654","1000 315","0 595","57 1000","0 141","187 0","1000 673","1000 577","1000 510","0 732","0 509","604 1000","406 1000","908 0","403 0","0 849","983 1000"}

    12

    Returns: 4943

  53. {"0 1000","1000 1000","1000 0","0 0"}

    {"1000 312","295 0","0 991","746 1000","185 0","0 569","712 0","513 1000","172 0","1000 972","786 0","1000 282","1000 577","722 1000","951 0","102 1000"}

    3

    Returns: -1

  54. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"307 40","281 240","138 270","260 99","40 234","226 180","227 300","127 150","120 120","322 320","192 40","178 220","261 240","217 300","40 260","294 320","287 320","304 40","128 150","290 72","126 190"}

    7

    Returns: 3907

  55. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"989 0","1000 81","525 0","422 1000","0 760","101 0","275 0","0 628","218 0","0 423","1000 741","0 542","0 953","474 0","0 533","215 1000","0 566","780 1000","231 1000","293 0","0 524","161 1000","0 968","1000 562","0 881","664 1000","0 472","304 0","0 133","0 840","350 0","1000 56","0 469","503 1000","105 1000","772 1000","98 1000","684 0","0 718","615 0","0 120","810 1000","0 684","393 1000","482 0","0 652","622 0","1000 782","1000 99","102 0"}

    16

    Returns: 5437

  56. {"0 1000","1000 1000","1000 0","0 0"}

    {"0 5","1000 761","0 890","1000 957","0 723","380 1000","1000 749","0 23","506 0","1000 403","1000 93","408 1000","0 755","0 649","0 455","1000 944","540 0","621 1000","925 0","224 1000","1000 735","0 844","955 0","341 0","0 304","890 0","582 1000","1000 232","1000 301","320 1000","223 0","0 206","0 181","198 0","310 1000","67 0","639 0","0 256","1000 842","871 1000"}

    13

    Returns: 5578

  57. {"40 360","40 100","70 100","70 40","240 40","240 80","130 80","130 100","170 100","170 90","240 90","240 180","120 180","120 150","170 150","170 120","70 120","70 200","90 200","90 150","110 150","110 190","260 190","260 40","390 40","390 70","290 70","290 240","190 240","190 220","120 220","120 270","200 270","200 300","300 300","300 270","330 270","330 180","360 180","360 320","250 320","250 340","250 370","150 370","150 320","170 320","170 300","70 300","70 360","63 360"}

    {"290 197","250 365","148 80","143 190","161 190","40 149","250 358","360 249","86 120","202 90","260 50","150 300","87 120","360 265","258 300","157 150","40 184","203 240","146 150","150 322","70 90","388 70","260 88"}

    7

    Returns: 4884

  58. {"0 0","176 0","379 0","458 0","985 0","986 0","1000 0","1000 1","1000 2","1000 382","1000 853","1000 932","1000 1000","983 1000","148 1000","11 1000","0 1000","0 985","0 184","0 12","0 5"}

    {"1000 821","1000 726","0 219","0 880","612 1000","1000 606","1000 11","1000 533","579 1000","497 1000","1000 255","0 200","309 1000","530 1000","1000 207","1000 956","307 0","1000 916","538 0","604 1000","310 0","1000 278","953 1000","462 0","1000 594","784 0","54 1000","1000 8","1000 69","895 1000","0 513","42 0","865 0","0 71","0 624","1000 423","837 0","1000 539","0 196","1000 758","252 0","1000 562"}

    14

    Returns: 5354

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: