A - Food Delivery
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
AtCoder社は冷めても美味しい料理をのんびり配達するフードデリバリーサービス AtCoder Foods を運営している。 このサービスでは、事前に配達の注文を沢山受け付けておき、複数の配達を一気に処理することで効率化を図っている。 現在のサービスエリアは二次元平面上の正方形領域 \{(x,y)\mid 0\leq x, y\leq 800\} で表され、中心の (400, 400) の地点にAtCoder社のオフィスがある。 今日は注文が 1000 件入っており、i (1\leq i\leq 1000) 番目の注文は (a_i, b_i) にあるレストランから (c_i, d_i) への配達依頼である。
配達員の一人である高橋くんの今日のノルマは50件の注文を処理することである。 高橋くんは 1000 件の注文の中からちょうど50件の部分集合 S\subseteq\{1,\cdots,1000\} を自由に選び、以下の条件を満たすルート (x_1,y_1),\cdots,(x_n,y_n) で配達を行う。
- 各 i\in S に対して、(a_i,b_i) を訪れた後に、(c_i, d_i) を訪れる。すなわち、(x_s,y_s)=(a_i,b_i)、(x_t,y_t)=(c_i,d_i)、s<t となる整数組 (s, t) が存在する。
- (x_1,y_1)=(x_n,y_n)=(400, 400)。
あるレストランで料理をピックアップした後、その料理を配達先に届ける前に別のレストランで料理をピックアップしたり、別の料理を先に届けても良い。 高橋くんは力持ちなので任意個の料理を同時に運ぶことが可能である。
(x_i,y_i) から (x_{i+1},y_{i+1}) への移動にはマンハッタン距離 |x_i-x_{i+1}|+|y_i-y_{i+1}| の時間がかかり、 配達ルートの総移動時間は T=\sum_{i=1}^{n-1} |x_i - x_{i+1}|+|y_i-y_{i+1}| となる。 総移動時間が出来るだけ短くなるように担当する注文 S の選択と配達ルートを最適化して欲しい。
得点
出力された配達ルートの総移動時間 T に対し、\mathrm{round}(10^8/(1000+T)) の得点が得られる。
テストケースは全部で 100 個あり、各テストケースの得点の合計が提出の得点となる。 1つ以上のテストケースで AC 以外の判定がされた場合、提出の得点は0点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、その得点を獲得した提出の早い方が上位となる。
入力
入力は以下の形式で標準入力から与えられる。
a_1 b_1 c_1 d_1
\vdots
a_{1000} b_{1000} c_{1000} d_{1000}
a_i, b_i, c_i, d_i はそれぞれ 0 以上 800 以下の整数値であり、(a_i, b_i) が配達元のレストランの座標、(c_i, d_i) が配達先の座標を表す。 (a_i,b_i)\neq (c_i,d_i) を満たすが、異なる注文 j について \{(a_i,b_i),(c_i,d_i)\}\cap\{(a_j,b_j),(c_j,d_j)\}\neq\emptyset となる可能性はある。
出力
選択した注文の集合を r_1,\cdots,r_m (1\leq r_i\leq 1000)、配達ルートを (x_1,y_1),\cdots,(x_n,y_n) (0\leq x_i,y_i\leq 800) としたとき、以下の形式で標準出力に出力せよ。
m r_1 \cdots r_m n x_1 y_1 \cdots x_n y_n
ビジュアライズに利用するために複数回の出力を行っても良い。 提出プログラムが複数回の出力をした場合、一番最後の出力のみが採点に使用される。 最後の出力は m=50 でなければならないが、途中段階での出力は m\neq 50 もビジュアライズのために許容されている。
入力生成方法
L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L,U) で表す。 各 i=1,\cdots,1000 に対して注文 (a_i, b_i, c_i, d_i) を以下のように生成する。
a_i=\mathrm{rand}(0, 800)、b_i=\mathrm{rand}(0, 800)、c_i=\mathrm{rand}(0, 800)、d_i=\mathrm{rand}(0, 800) を生成する。 マンハッタン距離 |a_i-c_i|+|b_i-d_i| が 100 未満の間、生成をやり直す。
入力例 1
406 19 347 786 4 689 659 189 96 89 424 397 523 617 212 413 453 664 592 230 582 457 46 186 32 80 671 402 298 742 653 538 681 91 152 276 730 442 375 423 772 789 347 232 688 445 99 358 475 111 593 277 178 196 431 383 9 518 747 560 641 116 272 493 536 591 52 643 546 121 328 203 618 75 452 281 257 746 579 470 475 417 232 454 90 95 355 119 10 388 410 304 355 159 724 244 720 258 414 313 747 43 652 63 632 138 739 313 531 476 39 744 302 262 790 345 550 77 402 558 786 533 149 571 673 310 111 393 563 395 128 47 92 728 594 613 737 324 382 261 727 244 83 733 288 175 785 34 733 597 128 174 787 446 212 522 367 459 661 366 673 60 273 695 341 234 349 29 212 1 532 391 177 524 413 243 483 321 200 417 4 477 315 373 143 6 474 485 749 353 164 196 465 400 18 330 242 533 212 220 599 525 484 643 62 693 85 428 619 166 519 73 463 581 756 740 462 552 426 51 386 724 113 655 610 26 619 307 335 560 109 429 493 787 610 634 675 393 733 288 487 626 646 621 479 151 369 346 756 372 679 686 86 56 584 532 251 126 361 764 352 111 498 98 609 728 748 321 299 709 646 556 269 290 245 735 782 341 384 341 562 763 499 107 397 261 289 480 56 442 688 238 294 38 297 423 286 186 138 561 376 13 764 470 489 186 357 254 617 498 309 551 244 213 684 126 689 613 214 393 668 688 58 707 57 131 568 360 603 27 734 592 209 480 5 669 39 645 224 686 596 270 357 217 727 266 454 569 254 721 359 423 546 333 525 501 557 157 10 786 769 743 653 191 157 260 438 744 682 632 156 515 428 103 243 117 185 746 670 474 372 493 2 39 128 412 548 564 445 639 175 752 157 2 581 463 38 443 21 333 133 329 323 440 114 149 494 363 636 360 729 588 344 85 713 145 556 486 307 722 527 42 746 628 305 509 270 135 603 256 286 446 698 774 204 210 270 677 409 676 400 769 403 49 563 582 636 375 225 380 728 547 160 478 258 274 209 739 79 395 757 21 269 526 443 650 42 487 682 343 6 385 292 40 47 128 714 314 106 193 101 438 330 740 725 556 442 503 199 614 376 424 519 565 158 661 673 673 141 491 617 245 772 505 438 107 83 263 404 10 400 409 575 735 451 711 25 555 395 643 697 423 625 496 543 683 655 703 491 332 748 75 191 180 697 646 50 221 202 757 147 774 614 739 167 324 782 331 502 683 316 11 309 163 737 725 67 241 684 406 509 597 114 686 249 776 31 673 259 576 129 323 739 521 283 259 790 181 265 667 240 514 690 239 724 333 752 777 713 145 558 51 438 404 468 226 722 382 289 299 494 363 412 539 603 241 12 688 245 3 728 742 538 686 60 22 730 668 633 381 603 572 736 137 800 227 671 401 562 448 340 222 270 67 555 504 404 82 360 505 120 744 395 680 676 159 149 76 54 761 576 337 768 37 98 281 21 658 486 726 310 529 292 315 136 683 768 606 435 284 113 748 405 360 2 450 345 719 303 321 276 528 0 251 341 174 577 717 480 82 540 262 184 367 590 11 422 612 155 584 247 79 584 467 12 763 163 291 127 289 372 469 544 8 622 71 567 504 15 481 516 291 251 444 84 462 456 649 388 766 211 353 537 568 557 770 472 128 544 202 541 541 212 511 744 158 49 188 601 366 646 6 49 757 425 488 196 143 41 186 614 464 147 477 473 33 89 794 355 74 500 792 760 335 681 18 738 167 570 435 376 695 472 628 39 611 563 86 790 738 729 507 219 70 75 413 85 415 514 426 315 261 623 578 602 98 673 248 179 685 331 95 484 669 312 239 672 780 470 480 475 13 105 750 700 520 243 232 792 618 737 732 676 0 282 754 85 434 107 76 190 703 480 796 545 431 740 677 304 334 662 272 412 782 287 123 395 111 192 575 772 143 711 559 385 394 683 406 107 464 193 360 211 151 17 795 464 188 275 316 565 740 89 16 644 255 163 281 21 487 305 168 192 270 334 599 18 104 311 43 112 354 521 163 83 575 618 356 484 248 530 597 513 342 172 104 556 118 620 634 601 517 87 560 43 421 641 85 628 185 220 363 422 535 239 759 194 174 359 774 739 555 759 796 655 24 552 793 644 175 296 317 67 335 296 422 197 279 396 405 17 568 313 147 638 489 347 268 226 49 587 360 624 128 124 630 67 708 542 617 384 277 667 653 478 266 627 466 265 52 577 473 346 175 209 672 596 68 420 617 151 272 285 256 723 117 774 382 518 89 43 193 604 468 170 522 46 108 483 115 200 14 785 772 29 733 317 8 228 204 690 755 696 671 4 2 593 181 485 445 597 283 409 689 31 296 590 357 407 578 556 427 239 61 402 27 43 294 376 413 733 746 709 70 7 60 642 303 238 216 586 61 360 493 480 592 75 205 443 271 57 698 168 722 436 560 800 752 265 765 102 148 420 766 729 109 218 238 590 369 8 362 480 467 537 549 83 516 441 440 289 137 785 746 573 238 731 4 470 543 396 672 594 474 654 351 76 681 488 695 655 36 78 480 244 732 333 636 216 153 113 459 64 29 376 248 634 370 78 200 348 232 688 438 405 702 436 529 232 482 173 177 736 180 475 567 400 684 527 609 375 685 733 677 7 79 770 3 426 435 610 76 321 638 338 134 690 213 50 458 277 620 653 791 72 684 291 146 237 569 695 762 325 215 170 27 394 614 116 604 318 499 56 94 449 152 729 263 354 137 165 798 379 292 633 257 703 765 722 340 175 121 791 380 68 37 525 249 83 182 56 181 86 605 321 539 619 106 699 621 233 484 546 146 778 460 599 105 333 70 440 379 250 764 41 135 672 469 518 718 178 544 542 759 282 11 337 178 716 388 287 338 188 744 491 371 310 96 151 599 215 319 576 294 719 563 424 527 791 626 613 580 397 745 687 236 59 401 98 229 677 164 112 288 758 647 315 152 728 253 449 100 203 351 497 304 630 190 385 584 275 121 485 195 125 59 407 218 27 562 306 409 644 245 792 670 606 697 110 651 484 741 121 693 317 202 186 7 513 520 0 600 356 734 679 412 175 440 131 95 415 67 114 300 441 90 9 12 674 82 633 526 712 162 295 289 649 246 695 383 493 342 275 75 487 566 271 177 239 694 512 646 139 435 458 104 77 467 132 71 165 298 10 83 138 425 409 579 372 61 187 194 729 348 61 578 614 663 491 430 343 307 483 464 11 477 335 501 778 151 703 313 346 532 281 588 722 765 297 591 594 600 23 79 123 207 197 685 279 603 408 436 136 742 792 773 310 596 74 507 72 38 46 38 612 99 753 320 655 156 535 457 391 497 193 600 310 270 337 295 125 564 669 430 242 360 512 382 533 295 33 495 360 717 614 523 604 25 630 506 667 368 639 397 174 273 207 180 572 300 457 312 798 165 246 623 71 259 687 689 242 91 311 336 59 288 760 319 254 329 340 17 435 600 256 158 185 561 521 148 786 571 609 793 776 281 531 645 619 355 591 752 78 20 498 484 678 555 632 363 423 605 508 488 295 366 34 333 389 454 763 546 585 164 680 73 63 276 499 29 270 57 529 595 706 329 539 222 571 303 590 579 127 198 597 16 702 580 791 216 156 172 552 330 146 744 4 785 18 249 160 395 191 784 440 284 29 790 306 536 63 355 658 216 335 468 155 662 657 439 726 699 342 26 314 730 442 509 339 760 385 309 681 737 289 732 452 14 223 545 596 345 277 694 94 676 680 719 378 596 263 254 385 566 242 528 266 269 98 350 692 524 770 309 209 596 436 268 421 7 735 790 413 620 547 732 64 795 592 153 705 16 177 511 560 28 125 45 270 759 0 533 780 310 339 723 226 28 739 183 317 666 26 270 254 785 535 726 470 750 15 220 258 594 30 589 302 17 593 606 547 338 272 58 668 571 393 21 441 687 742 363 528 67 311 756 477 138 508 786 197 579 351 667 505 555 750 58 691 653 508 676 489 670 304 151 134 27 72 292 109 747 179 35 667 369 761 163 244 131 447 513 434 526 762 353 534 528 760 410 196 139 798 644 489 268 594 338 259 788 342 131 427 143 775 508 780 762 655 792 313 748 441 463 554 686 333 150 426 488 7 688 586 301 227 300 560 80 743 522 680 601 357 234 519 613 567 369 159 71 515 720 462 64 81 349 433 145 735 132 123 628 515 609 638 730 153 726 76 101 389 79 94 478 627 59 644 388 714 631 705 599 367 695 134 145 680 19 588 633 192 433 439 463 248 682 565 203 67 612 251 745 621 362 122 181 699 529 690 645 20 211 274 463 128 612 77 684 381 740 181 61 768 787 437 381 652 749 626 714 379 376 533 531 141 774 488 616 789 550 162 409 351 230 631 319 723 459 507 208 551 615 213 90 536 35 335 512 578 50 676 507 695 194 402 799 30 34 752 75 194 351 211 385 405 353 221 78 56 231 363 450 339 61 278 539 797 651 702 81 206 112 631 86 256 592 103 528 416 429 712 728 126 180 617 421 782 539 284 769 21 736 761 108 4 692 691 5 350 488 318 283 49 676 690 674 50 87 519 427 159 234 515 186 576 31 114 616 430 742 773 26 703 608 577 727 200 636 779 43 222 626 488 694 548 83 416 477 235 670 779 662 433 526 365 467 471 183 286 225 230 626 267 562 414 365 214 24 4 536 710 328 57 272 651 157 595 319 670 434 132 752 680 497 568 705 387 123 664 628 106 387 717 763 474 717 23 370 565 401 60 230 574 414 788 593 617 508 185 433 791 383 693 768 21 557 461 56 11 506 173 699 7 540 245 665 536 628 262 212 484 463 116 582 34 410 318 611 430 457 677 254 770 83 614 578 796 24 565 485 263 401 88 237 81 704 571 177 287 77 531 361 400 248 25 39 212 427 563 195 558 628 317 756 124 324 394 532 524 244 371 211 484 560 167 468 735 616 632 61 146 537 601 657 524 525 509 31 670 32 484 19 707 12 50 612 241 61 549 231 740 694 562 544 392 161 694 197 399 692 18 223 578 276 334 481 303 121 776 356 337 317 324 475 490 284 658 486 139 468 538 112 693 4 590 464 505 29 70 593 194 677 643 324 295 283 278 465 561 631 700 745 645 93 483 353 23 657 43 440 581 368 338 664 233 95 448 539 426 790 109 32 310 325 79 23 290 390 415 258 134 646 143 256 394 252 155 712 366 259 226 436 55 432 723 383 732 183 78 621 336 158 18 318 137 748 105 117 569 667 46 288 502 767 121 406 348 91 578 395 494 98 472 189 177 739 47 378 599 428 10 357 241 258 386 183 36 207 279 97 797 111 176 290 492 745 282 594 213 631 567 623 162 134 744 587 247 766 122 694 60 118 608 658 679 562 763 233 187 8 476 204 557 713 336 792 72 720 187 733 686 484 351 182 19 795 396 128 687 774 368 626 101 630 291 694 569 584 197 372 440 326 143 713 192 726 408 462 387 344 661 151 443 248 47 677 323 590 422 198 72 601 686 175 671 613 303 443 32 604 493 290 245 26 395 680 25 248 500 799 36 456 333 548 477 733 20 767 216 469 711 628 744 797 391 457 372 374 770 379 240 751 208 642 263 715 652 31 792 285 185 497 691 272 494 628 452 135 55 140 537 640 308 459 509 19 543 401 207 403 503 210 117 360 481 767 115 252 199 271 1 474 262 420 58 160 570 396 474 693 663 599 522 66 550 755 449 187 301 686 576 751 419 279 188 593 466 772 614 205 301 800 116 365 422 149 236 677 429 666 623 581 330 90 524 57 306 23 73 576 192 26 548 766 782 218 689 255 721 352 341 629 661 737 238 90 655 650 443 411 41 603 84 295 435 412 411 215 485 425 200 757 28 419 684 58 457 363 300 449 471 153 671 38 291 88 84 252 673 222 371 579 570 34 355 600 106 336 134 278 324 670 264 96 587 237 625 800 438 307 142 82 547 236 479 773 322 581 309 783 720 27 70 217 197 631 130 69 663 359 237 430 448 544 799 49 794 569 160 232 326 336 634 668 609 54 293 34 537 29 534 218 601 630 549 106 300 136 171 729 243 574 453 363 179 374 3 487 567 626 798 149 117 37 63 325 135 707 5 216 478 692 716 430 781 117 316 299 588 447 748 186 115 654 467 719 522 244 769 147 395 589 117 480 309 247 93 190 505 55 719 683 474 410 602 549 16 241 395 571 584 472 760 751 205 523 464 148 491 724 413 510 37 503 366 276 389 45 367 602 450 286 305 341 648 128 394 339 608 401 504 513 304 190 555 39 791 272 405 6 208 62 701 666 736 218 677 440 791 317 75 187 752 276 474 626 92 223 103 754 49 429 666 738 759 326 231 255 390 257 310 44 562 230 169 561 768 637 333 555 36 62 407 397 33 799 76 543 383 716 272 181 118 673 556 521 359 688 610 663 167 198 360 752 52 781 324 605 286 69 183 10 453 616 288 702 260 290 571 79 31 353 500 454 277 375 481 356 524 605 739 398 580 342 663 24 757 422 82 212 639 197 518 157 586 212 680 418 49 254 371 750 404 555 528 615 617 765 28 283 472 136 410 149 26 524 504 232 579 665 122 198 298 206 794 453 635 574 45 640 104 177 734 731 672 661 489 629 186 536 493 6 239 214 204 656 524 236 140 578 107 458 452 277 629 159 708 238 270 101 634 570 159 215 291 578 595 394 367 530 700 328 345 486 648 120 194 34 463 323 587 408 493 654 727 576 483 344 615 328 130 553 100 417 376 417 562 583 663 419 130 302 306 577 304 38 69 54 430 760 445 450 674 209 648 531 461 521 604 522 644 43 527 164 595 185 795 739 611 136 646 277 722 740 169 797 623 422 759 616 383 110 83 149 796 507 596 299 194 347 489 344 146 727 36 486 559 656 445 394 522 462 407 367 196 154 21 88 227 462 447 88 347 194 426 139 38 737 79 455 697 299 686 490 517 378 572 755 121 209 261 463 386 434 565 430 615 427 776 720 48 212 148 390 245 666 416 304 242 120 560 660 208 3 186 177 502 473 225 659 456 343 506 144 603 647 654 4 582 496 488 274 501 717 635 305 789 697 416 394 497 617 758 467 354 146 27 98 650 190 136 197 131 615 747 692 582 474 684 8 637 313 164 690 657 734 283 22 551 149 769 589 507 475 226 614 619 28 332 208 540 42 89 575 264 516 464 461 5 361 706 73 404 353 314 544 761 104 395 263 166 763 268 417 600 395 179 241 330 196 579 248 298 495 68 652 607 430 325 631 249 653 444 673 538 471 264 333 191 441 754 751 460 138 41 28 372 471 305 324 478 70 401 144 535 531 80 86 322 564 778 148 295 149 760 508 157 793 617 720 276 5 179 478 15 388 3 120 684 351 389 192 551 656 85 218 68 47 120 456 401 366 545 651 735 541 524 663 468 441 606 387 39 193 425 530 470 783 543 103 167 154 113 681 361 663 315 741 562 153 137 7 609 726 515 407 743 120 780 535 702 123 573 769 60 275 120 600 483 768 700 274 262 590 542 615 605 482 530 666 287 516 757 407 96 257 378 134 379 410 494 369 69 149 324 119 61 663 341 378 206 538 551 252 703 724 702 575 757 688 628 221 592 636 560 130 321 674 711 600 609 604 552 204 193 390 434 208 319 273 210 590 459 91 390 46 322 589 552 316 655 415 685 758 163 367 725 220 692 439 346 97 617 0 348 791 299 374 302 549 44 202 672 120 49 169 789 558 268 630 209 671 496 394 550 20 798 172 327 185 367 212 617 31 331 657 182 324 386 241 245 733 739 93 428 129 558 403 747 470 743 148 201 178 392 214 620 407 510 128 487 14 707 662 716 259 201 429 116 631 458 176 654 30 239 276 402 231 377 342 475 789 315 67 290 587 57 158 54 396 28 505 114 4 79 240 566 534 592 739 493 393 130 152 227 268 524 268 334 541 693 637 206 587 608 246 440 124 105 676 151 420 759 413 433 553 470 340 226 344 731 283 456 136 7 166 725 294 107 776 86 288 103 798 738 23 36 458 274 569 432 257 748 777 88 391 426 345 792 221 519 408 715 473 42 508 483 354 706 773 675 417 481 286 33 332 483 493 450 16 182 180 792 381 775 170 767 12 783 473 146 790 495 726 339 440 352 314 708 681 669 105 694 310 678 0 634 262 73 300 415 165 744 301 379 338 731 231 261 142 288 445 340 193 651 274 757 206 473 782 521 398 605 601 327 80 247 794 172 49 169 216 592 525 343 468 337 566 206 136 44 325 260 49 444 392 71 492 498 47 105 52 104 665 382 280 469 455 131 133 616 501 716 317 652 134 533 756 363 646 297 396 389 525 157 131 20 7 506 43 263 200 245 98 535 582 249 107 326 76 543 570 628 392 751 360 39 261 208 131 381 412 708 532 591 149 221 660 14 167 569 382 698 603 204 90 313 159 456 26 481 147 557 566 223 492 396 236 27 86 320 135 132 736 787 237 559 717 690 524 151 566 237 300 334 89 171 382 18 781 248 679 599 396 490 575 362 402 124 698 515 54 141 252 637 327 499 662 662 158 784 459 391 188 53 500 192 564 406 445 451 514 125 668 721 4 101 559 128 718 697 57 110 676 412 581 284 202 330 283 413 676 752 530 77 469 510 168 561 159 9 213 107 361 757 742 649 102 769 534 124 353 414 637 81 485 530 465 522 562 774 564 335 179 65 222 741 330 243 654 549 429 21 497 72 770 174 669 420 288 193 530 183 15 392 130 399 493 487 284 720 528 28 190 7 238 403 239 347 227 215 743 254 131 478 485 713 627 215 298 112 223 86 78 747 781 725 333 783 107 53 108 677 369 243 790 95 107 272 322 20 108 72 316 337 404 796 513 593 500 676 776 697 706 43 133 12 762 546 273 249 207 71 60 574 154 698 108 782 522 59 48 383 644 64 709 559 629 233 126 676 53 267 653 490 46 48 664 362 796 210 476 753 144 748 625 288 529 359 27 468 405 381 639 216 748 403 738 475 61 634 181 178 4 354 70 732 525 765 393
出力例 1
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 102 400 400 406 19 347 786 4 689 659 189 96 89 424 397 523 617 212 413 453 664 592 230 582 457 46 186 32 80 671 402 298 742 653 538 681 91 152 276 730 442 375 423 772 789 347 232 688 445 99 358 475 111 593 277 178 196 431 383 9 518 747 560 641 116 272 493 536 591 52 643 546 121 328 203 618 75 452 281 257 746 579 470 475 417 232 454 90 95 355 119 10 388 410 304 355 159 724 244 720 258 414 313 747 43 652 63 632 138 739 313 531 476 39 744 302 262 790 345 550 77 402 558 786 533 149 571 673 310 111 393 563 395 128 47 92 728 594 613 737 324 382 261 727 244 83 733 288 175 785 34 733 597 128 174 787 446 212 522 367 459 661 366 673 60 273 695 341 234 349 29 212 1 532 391 177 524 413 243 483 321 200 417 4 477 315 373 143 6 474 485 749 353 164 196 465 400 18 330 242 533 212 220 400 400
Problem Statement
AtCoder Inc. operates a food delivery service, AtCoder Foods, that leisurely delivers food that tastes good even if it gets cold. This service receives a large number of delivery orders in advance, and processes multiple deliveries simultaneously to improve efficiency. The current service area is represented as a square area \{(x,y)\mid 0\leq x, y\leq 800\} on a two-dimensional plane, with AtCoder's office located at the center (400, 400). There are 1000 orders today, and the i (1\leq i\leq 1000)-th order is a food delivery request from a restaurant in (a_i, b_i) to a location in (c_i, d_i).
Today's quota for Takahashi, a delivery man, is to process 50 orders. He can freely choose a subset S\subseteq\{1,\cdots,1000\} of size exactly 50 from the 1000 orders and deliver on a route (x_1,y_1),\cdots,(x_n,y_n) satisfying the following conditions.
- For each i\in S, visit (c_i, d_i) after visiting (a_i,b_i). That is, there exists an integer pair (s, t) such that (x_s,y_s)=(a_i,b_i), (x_t,y_t)=(c_i,d_i), and s<t.
- (x_1,y_1)=(x_n,y_n)=(400, 400).
After picking up food at one restaurant, he may pick up food at another restaurant or deliver food to another destination before delivering that food to the destination. He is so powerful that he can carry arbitrary numbers of dishes simultaneously.
Moving from (x_i,y_i) to (x_{i+1},y_{i+1}) takes time equal to the Manhattan distance |x_i-x_{i+1}|+|y_i-y_{i+1}|, and the total travel time for the delivery route is T=\sum_{i=1}^{n-1} |x_i - x_{i+1}|+|y_i - y_{i+1}|. Please optimize S and delivery routes so that the total travel time is as short as possible.
Scoring
For the total travel time T of the output delivery route, you will get a score of \mathrm{round}(10^8/(1000+T)).
There are 100 test cases, and the score of a submission is the total score for each test case. If you get a result other than AC for one or more test cases, the score of the submission will be zero. The highest score obtained during the contest time will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, the ranking will be determined by the submission time of the submission that received that score.
Input
Input is given from Standard Input in the following format:
a_1 b_1 c_1 d_1
\vdots
a_{1000} b_{1000} c_{1000} d_{1000}
Each a_i, b_i, c_i, d_i is an integer between 0 and 800, inclusive, where (a_i, b_i) represents the coordinates of the restaurant, and (c_i, d_i) represents the coordinates of the destination. (a_i,b_i)\neq (c_i,d_i) is satisfied, but for different orders j, there is a possibility that \{(a_i,b_i),(c_i,d_i)\}\cap\{(a_j,b_j),(c_j,d_j)\}\neq\emptyset.
Output
Let the set of chosen orders be r_1,\cdots,r_m (1\leq r_i\leq 1000), and the delivery route be (x_1,y_1),\cdots,(x_n,y_n) (0\leq x_i,y_i\leq 800), output to Standard Output in the following format.
m r_1 \cdots r_m n x_1 y_1 \cdots x_n y_n
You may output multiple times for visualization purposes. If your program outputs multiple times, only the last output will be used for scoring. The final output must satisfy m=50, but intermediate outputs with m\neq 50 are allowed for visualization.
Input Generation
Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive. For each i=1,\cdots,1000, we generate an order (a_i, b_i, c_i, d_i) as follows.
We generate a_i=\mathrm{rand}(0, 800), b_i=\mathrm{rand}(0, 800), c_i=\mathrm{rand}(0, 800), and d_i=\mathrm{rand}(0, 800). Redo the generation as long as the Manhattan distance |a_i-c_i|+|b_i-d_i| is less than 100.
Tools (Input generator and visualizer)
- Local version: You need a compilation environment of Rust language.
- Web version: This is more powerful than the local version and can display animations.
Sharing visualization results is not allowed until the end of the contest.
Sample Input 1
406 19 347 786 4 689 659 189 96 89 424 397 523 617 212 413 453 664 592 230 582 457 46 186 32 80 671 402 298 742 653 538 681 91 152 276 730 442 375 423 772 789 347 232 688 445 99 358 475 111 593 277 178 196 431 383 9 518 747 560 641 116 272 493 536 591 52 643 546 121 328 203 618 75 452 281 257 746 579 470 475 417 232 454 90 95 355 119 10 388 410 304 355 159 724 244 720 258 414 313 747 43 652 63 632 138 739 313 531 476 39 744 302 262 790 345 550 77 402 558 786 533 149 571 673 310 111 393 563 395 128 47 92 728 594 613 737 324 382 261 727 244 83 733 288 175 785 34 733 597 128 174 787 446 212 522 367 459 661 366 673 60 273 695 341 234 349 29 212 1 532 391 177 524 413 243 483 321 200 417 4 477 315 373 143 6 474 485 749 353 164 196 465 400 18 330 242 533 212 220 599 525 484 643 62 693 85 428 619 166 519 73 463 581 756 740 462 552 426 51 386 724 113 655 610 26 619 307 335 560 109 429 493 787 610 634 675 393 733 288 487 626 646 621 479 151 369 346 756 372 679 686 86 56 584 532 251 126 361 764 352 111 498 98 609 728 748 321 299 709 646 556 269 290 245 735 782 341 384 341 562 763 499 107 397 261 289 480 56 442 688 238 294 38 297 423 286 186 138 561 376 13 764 470 489 186 357 254 617 498 309 551 244 213 684 126 689 613 214 393 668 688 58 707 57 131 568 360 603 27 734 592 209 480 5 669 39 645 224 686 596 270 357 217 727 266 454 569 254 721 359 423 546 333 525 501 557 157 10 786 769 743 653 191 157 260 438 744 682 632 156 515 428 103 243 117 185 746 670 474 372 493 2 39 128 412 548 564 445 639 175 752 157 2 581 463 38 443 21 333 133 329 323 440 114 149 494 363 636 360 729 588 344 85 713 145 556 486 307 722 527 42 746 628 305 509 270 135 603 256 286 446 698 774 204 210 270 677 409 676 400 769 403 49 563 582 636 375 225 380 728 547 160 478 258 274 209 739 79 395 757 21 269 526 443 650 42 487 682 343 6 385 292 40 47 128 714 314 106 193 101 438 330 740 725 556 442 503 199 614 376 424 519 565 158 661 673 673 141 491 617 245 772 505 438 107 83 263 404 10 400 409 575 735 451 711 25 555 395 643 697 423 625 496 543 683 655 703 491 332 748 75 191 180 697 646 50 221 202 757 147 774 614 739 167 324 782 331 502 683 316 11 309 163 737 725 67 241 684 406 509 597 114 686 249 776 31 673 259 576 129 323 739 521 283 259 790 181 265 667 240 514 690 239 724 333 752 777 713 145 558 51 438 404 468 226 722 382 289 299 494 363 412 539 603 241 12 688 245 3 728 742 538 686 60 22 730 668 633 381 603 572 736 137 800 227 671 401 562 448 340 222 270 67 555 504 404 82 360 505 120 744 395 680 676 159 149 76 54 761 576 337 768 37 98 281 21 658 486 726 310 529 292 315 136 683 768 606 435 284 113 748 405 360 2 450 345 719 303 321 276 528 0 251 341 174 577 717 480 82 540 262 184 367 590 11 422 612 155 584 247 79 584 467 12 763 163 291 127 289 372 469 544 8 622 71 567 504 15 481 516 291 251 444 84 462 456 649 388 766 211 353 537 568 557 770 472 128 544 202 541 541 212 511 744 158 49 188 601 366 646 6 49 757 425 488 196 143 41 186 614 464 147 477 473 33 89 794 355 74 500 792 760 335 681 18 738 167 570 435 376 695 472 628 39 611 563 86 790 738 729 507 219 70 75 413 85 415 514 426 315 261 623 578 602 98 673 248 179 685 331 95 484 669 312 239 672 780 470 480 475 13 105 750 700 520 243 232 792 618 737 732 676 0 282 754 85 434 107 76 190 703 480 796 545 431 740 677 304 334 662 272 412 782 287 123 395 111 192 575 772 143 711 559 385 394 683 406 107 464 193 360 211 151 17 795 464 188 275 316 565 740 89 16 644 255 163 281 21 487 305 168 192 270 334 599 18 104 311 43 112 354 521 163 83 575 618 356 484 248 530 597 513 342 172 104 556 118 620 634 601 517 87 560 43 421 641 85 628 185 220 363 422 535 239 759 194 174 359 774 739 555 759 796 655 24 552 793 644 175 296 317 67 335 296 422 197 279 396 405 17 568 313 147 638 489 347 268 226 49 587 360 624 128 124 630 67 708 542 617 384 277 667 653 478 266 627 466 265 52 577 473 346 175 209 672 596 68 420 617 151 272 285 256 723 117 774 382 518 89 43 193 604 468 170 522 46 108 483 115 200 14 785 772 29 733 317 8 228 204 690 755 696 671 4 2 593 181 485 445 597 283 409 689 31 296 590 357 407 578 556 427 239 61 402 27 43 294 376 413 733 746 709 70 7 60 642 303 238 216 586 61 360 493 480 592 75 205 443 271 57 698 168 722 436 560 800 752 265 765 102 148 420 766 729 109 218 238 590 369 8 362 480 467 537 549 83 516 441 440 289 137 785 746 573 238 731 4 470 543 396 672 594 474 654 351 76 681 488 695 655 36 78 480 244 732 333 636 216 153 113 459 64 29 376 248 634 370 78 200 348 232 688 438 405 702 436 529 232 482 173 177 736 180 475 567 400 684 527 609 375 685 733 677 7 79 770 3 426 435 610 76 321 638 338 134 690 213 50 458 277 620 653 791 72 684 291 146 237 569 695 762 325 215 170 27 394 614 116 604 318 499 56 94 449 152 729 263 354 137 165 798 379 292 633 257 703 765 722 340 175 121 791 380 68 37 525 249 83 182 56 181 86 605 321 539 619 106 699 621 233 484 546 146 778 460 599 105 333 70 440 379 250 764 41 135 672 469 518 718 178 544 542 759 282 11 337 178 716 388 287 338 188 744 491 371 310 96 151 599 215 319 576 294 719 563 424 527 791 626 613 580 397 745 687 236 59 401 98 229 677 164 112 288 758 647 315 152 728 253 449 100 203 351 497 304 630 190 385 584 275 121 485 195 125 59 407 218 27 562 306 409 644 245 792 670 606 697 110 651 484 741 121 693 317 202 186 7 513 520 0 600 356 734 679 412 175 440 131 95 415 67 114 300 441 90 9 12 674 82 633 526 712 162 295 289 649 246 695 383 493 342 275 75 487 566 271 177 239 694 512 646 139 435 458 104 77 467 132 71 165 298 10 83 138 425 409 579 372 61 187 194 729 348 61 578 614 663 491 430 343 307 483 464 11 477 335 501 778 151 703 313 346 532 281 588 722 765 297 591 594 600 23 79 123 207 197 685 279 603 408 436 136 742 792 773 310 596 74 507 72 38 46 38 612 99 753 320 655 156 535 457 391 497 193 600 310 270 337 295 125 564 669 430 242 360 512 382 533 295 33 495 360 717 614 523 604 25 630 506 667 368 639 397 174 273 207 180 572 300 457 312 798 165 246 623 71 259 687 689 242 91 311 336 59 288 760 319 254 329 340 17 435 600 256 158 185 561 521 148 786 571 609 793 776 281 531 645 619 355 591 752 78 20 498 484 678 555 632 363 423 605 508 488 295 366 34 333 389 454 763 546 585 164 680 73 63 276 499 29 270 57 529 595 706 329 539 222 571 303 590 579 127 198 597 16 702 580 791 216 156 172 552 330 146 744 4 785 18 249 160 395 191 784 440 284 29 790 306 536 63 355 658 216 335 468 155 662 657 439 726 699 342 26 314 730 442 509 339 760 385 309 681 737 289 732 452 14 223 545 596 345 277 694 94 676 680 719 378 596 263 254 385 566 242 528 266 269 98 350 692 524 770 309 209 596 436 268 421 7 735 790 413 620 547 732 64 795 592 153 705 16 177 511 560 28 125 45 270 759 0 533 780 310 339 723 226 28 739 183 317 666 26 270 254 785 535 726 470 750 15 220 258 594 30 589 302 17 593 606 547 338 272 58 668 571 393 21 441 687 742 363 528 67 311 756 477 138 508 786 197 579 351 667 505 555 750 58 691 653 508 676 489 670 304 151 134 27 72 292 109 747 179 35 667 369 761 163 244 131 447 513 434 526 762 353 534 528 760 410 196 139 798 644 489 268 594 338 259 788 342 131 427 143 775 508 780 762 655 792 313 748 441 463 554 686 333 150 426 488 7 688 586 301 227 300 560 80 743 522 680 601 357 234 519 613 567 369 159 71 515 720 462 64 81 349 433 145 735 132 123 628 515 609 638 730 153 726 76 101 389 79 94 478 627 59 644 388 714 631 705 599 367 695 134 145 680 19 588 633 192 433 439 463 248 682 565 203 67 612 251 745 621 362 122 181 699 529 690 645 20 211 274 463 128 612 77 684 381 740 181 61 768 787 437 381 652 749 626 714 379 376 533 531 141 774 488 616 789 550 162 409 351 230 631 319 723 459 507 208 551 615 213 90 536 35 335 512 578 50 676 507 695 194 402 799 30 34 752 75 194 351 211 385 405 353 221 78 56 231 363 450 339 61 278 539 797 651 702 81 206 112 631 86 256 592 103 528 416 429 712 728 126 180 617 421 782 539 284 769 21 736 761 108 4 692 691 5 350 488 318 283 49 676 690 674 50 87 519 427 159 234 515 186 576 31 114 616 430 742 773 26 703 608 577 727 200 636 779 43 222 626 488 694 548 83 416 477 235 670 779 662 433 526 365 467 471 183 286 225 230 626 267 562 414 365 214 24 4 536 710 328 57 272 651 157 595 319 670 434 132 752 680 497 568 705 387 123 664 628 106 387 717 763 474 717 23 370 565 401 60 230 574 414 788 593 617 508 185 433 791 383 693 768 21 557 461 56 11 506 173 699 7 540 245 665 536 628 262 212 484 463 116 582 34 410 318 611 430 457 677 254 770 83 614 578 796 24 565 485 263 401 88 237 81 704 571 177 287 77 531 361 400 248 25 39 212 427 563 195 558 628 317 756 124 324 394 532 524 244 371 211 484 560 167 468 735 616 632 61 146 537 601 657 524 525 509 31 670 32 484 19 707 12 50 612 241 61 549 231 740 694 562 544 392 161 694 197 399 692 18 223 578 276 334 481 303 121 776 356 337 317 324 475 490 284 658 486 139 468 538 112 693 4 590 464 505 29 70 593 194 677 643 324 295 283 278 465 561 631 700 745 645 93 483 353 23 657 43 440 581 368 338 664 233 95 448 539 426 790 109 32 310 325 79 23 290 390 415 258 134 646 143 256 394 252 155 712 366 259 226 436 55 432 723 383 732 183 78 621 336 158 18 318 137 748 105 117 569 667 46 288 502 767 121 406 348 91 578 395 494 98 472 189 177 739 47 378 599 428 10 357 241 258 386 183 36 207 279 97 797 111 176 290 492 745 282 594 213 631 567 623 162 134 744 587 247 766 122 694 60 118 608 658 679 562 763 233 187 8 476 204 557 713 336 792 72 720 187 733 686 484 351 182 19 795 396 128 687 774 368 626 101 630 291 694 569 584 197 372 440 326 143 713 192 726 408 462 387 344 661 151 443 248 47 677 323 590 422 198 72 601 686 175 671 613 303 443 32 604 493 290 245 26 395 680 25 248 500 799 36 456 333 548 477 733 20 767 216 469 711 628 744 797 391 457 372 374 770 379 240 751 208 642 263 715 652 31 792 285 185 497 691 272 494 628 452 135 55 140 537 640 308 459 509 19 543 401 207 403 503 210 117 360 481 767 115 252 199 271 1 474 262 420 58 160 570 396 474 693 663 599 522 66 550 755 449 187 301 686 576 751 419 279 188 593 466 772 614 205 301 800 116 365 422 149 236 677 429 666 623 581 330 90 524 57 306 23 73 576 192 26 548 766 782 218 689 255 721 352 341 629 661 737 238 90 655 650 443 411 41 603 84 295 435 412 411 215 485 425 200 757 28 419 684 58 457 363 300 449 471 153 671 38 291 88 84 252 673 222 371 579 570 34 355 600 106 336 134 278 324 670 264 96 587 237 625 800 438 307 142 82 547 236 479 773 322 581 309 783 720 27 70 217 197 631 130 69 663 359 237 430 448 544 799 49 794 569 160 232 326 336 634 668 609 54 293 34 537 29 534 218 601 630 549 106 300 136 171 729 243 574 453 363 179 374 3 487 567 626 798 149 117 37 63 325 135 707 5 216 478 692 716 430 781 117 316 299 588 447 748 186 115 654 467 719 522 244 769 147 395 589 117 480 309 247 93 190 505 55 719 683 474 410 602 549 16 241 395 571 584 472 760 751 205 523 464 148 491 724 413 510 37 503 366 276 389 45 367 602 450 286 305 341 648 128 394 339 608 401 504 513 304 190 555 39 791 272 405 6 208 62 701 666 736 218 677 440 791 317 75 187 752 276 474 626 92 223 103 754 49 429 666 738 759 326 231 255 390 257 310 44 562 230 169 561 768 637 333 555 36 62 407 397 33 799 76 543 383 716 272 181 118 673 556 521 359 688 610 663 167 198 360 752 52 781 324 605 286 69 183 10 453 616 288 702 260 290 571 79 31 353 500 454 277 375 481 356 524 605 739 398 580 342 663 24 757 422 82 212 639 197 518 157 586 212 680 418 49 254 371 750 404 555 528 615 617 765 28 283 472 136 410 149 26 524 504 232 579 665 122 198 298 206 794 453 635 574 45 640 104 177 734 731 672 661 489 629 186 536 493 6 239 214 204 656 524 236 140 578 107 458 452 277 629 159 708 238 270 101 634 570 159 215 291 578 595 394 367 530 700 328 345 486 648 120 194 34 463 323 587 408 493 654 727 576 483 344 615 328 130 553 100 417 376 417 562 583 663 419 130 302 306 577 304 38 69 54 430 760 445 450 674 209 648 531 461 521 604 522 644 43 527 164 595 185 795 739 611 136 646 277 722 740 169 797 623 422 759 616 383 110 83 149 796 507 596 299 194 347 489 344 146 727 36 486 559 656 445 394 522 462 407 367 196 154 21 88 227 462 447 88 347 194 426 139 38 737 79 455 697 299 686 490 517 378 572 755 121 209 261 463 386 434 565 430 615 427 776 720 48 212 148 390 245 666 416 304 242 120 560 660 208 3 186 177 502 473 225 659 456 343 506 144 603 647 654 4 582 496 488 274 501 717 635 305 789 697 416 394 497 617 758 467 354 146 27 98 650 190 136 197 131 615 747 692 582 474 684 8 637 313 164 690 657 734 283 22 551 149 769 589 507 475 226 614 619 28 332 208 540 42 89 575 264 516 464 461 5 361 706 73 404 353 314 544 761 104 395 263 166 763 268 417 600 395 179 241 330 196 579 248 298 495 68 652 607 430 325 631 249 653 444 673 538 471 264 333 191 441 754 751 460 138 41 28 372 471 305 324 478 70 401 144 535 531 80 86 322 564 778 148 295 149 760 508 157 793 617 720 276 5 179 478 15 388 3 120 684 351 389 192 551 656 85 218 68 47 120 456 401 366 545 651 735 541 524 663 468 441 606 387 39 193 425 530 470 783 543 103 167 154 113 681 361 663 315 741 562 153 137 7 609 726 515 407 743 120 780 535 702 123 573 769 60 275 120 600 483 768 700 274 262 590 542 615 605 482 530 666 287 516 757 407 96 257 378 134 379 410 494 369 69 149 324 119 61 663 341 378 206 538 551 252 703 724 702 575 757 688 628 221 592 636 560 130 321 674 711 600 609 604 552 204 193 390 434 208 319 273 210 590 459 91 390 46 322 589 552 316 655 415 685 758 163 367 725 220 692 439 346 97 617 0 348 791 299 374 302 549 44 202 672 120 49 169 789 558 268 630 209 671 496 394 550 20 798 172 327 185 367 212 617 31 331 657 182 324 386 241 245 733 739 93 428 129 558 403 747 470 743 148 201 178 392 214 620 407 510 128 487 14 707 662 716 259 201 429 116 631 458 176 654 30 239 276 402 231 377 342 475 789 315 67 290 587 57 158 54 396 28 505 114 4 79 240 566 534 592 739 493 393 130 152 227 268 524 268 334 541 693 637 206 587 608 246 440 124 105 676 151 420 759 413 433 553 470 340 226 344 731 283 456 136 7 166 725 294 107 776 86 288 103 798 738 23 36 458 274 569 432 257 748 777 88 391 426 345 792 221 519 408 715 473 42 508 483 354 706 773 675 417 481 286 33 332 483 493 450 16 182 180 792 381 775 170 767 12 783 473 146 790 495 726 339 440 352 314 708 681 669 105 694 310 678 0 634 262 73 300 415 165 744 301 379 338 731 231 261 142 288 445 340 193 651 274 757 206 473 782 521 398 605 601 327 80 247 794 172 49 169 216 592 525 343 468 337 566 206 136 44 325 260 49 444 392 71 492 498 47 105 52 104 665 382 280 469 455 131 133 616 501 716 317 652 134 533 756 363 646 297 396 389 525 157 131 20 7 506 43 263 200 245 98 535 582 249 107 326 76 543 570 628 392 751 360 39 261 208 131 381 412 708 532 591 149 221 660 14 167 569 382 698 603 204 90 313 159 456 26 481 147 557 566 223 492 396 236 27 86 320 135 132 736 787 237 559 717 690 524 151 566 237 300 334 89 171 382 18 781 248 679 599 396 490 575 362 402 124 698 515 54 141 252 637 327 499 662 662 158 784 459 391 188 53 500 192 564 406 445 451 514 125 668 721 4 101 559 128 718 697 57 110 676 412 581 284 202 330 283 413 676 752 530 77 469 510 168 561 159 9 213 107 361 757 742 649 102 769 534 124 353 414 637 81 485 530 465 522 562 774 564 335 179 65 222 741 330 243 654 549 429 21 497 72 770 174 669 420 288 193 530 183 15 392 130 399 493 487 284 720 528 28 190 7 238 403 239 347 227 215 743 254 131 478 485 713 627 215 298 112 223 86 78 747 781 725 333 783 107 53 108 677 369 243 790 95 107 272 322 20 108 72 316 337 404 796 513 593 500 676 776 697 706 43 133 12 762 546 273 249 207 71 60 574 154 698 108 782 522 59 48 383 644 64 709 559 629 233 126 676 53 267 653 490 46 48 664 362 796 210 476 753 144 748 625 288 529 359 27 468 405 381 639 216 748 403 738 475 61 634 181 178 4 354 70 732 525 765 393
Sample Output 1
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 102 400 400 406 19 347 786 4 689 659 189 96 89 424 397 523 617 212 413 453 664 592 230 582 457 46 186 32 80 671 402 298 742 653 538 681 91 152 276 730 442 375 423 772 789 347 232 688 445 99 358 475 111 593 277 178 196 431 383 9 518 747 560 641 116 272 493 536 591 52 643 546 121 328 203 618 75 452 281 257 746 579 470 475 417 232 454 90 95 355 119 10 388 410 304 355 159 724 244 720 258 414 313 747 43 652 63 632 138 739 313 531 476 39 744 302 262 790 345 550 77 402 558 786 533 149 571 673 310 111 393 563 395 128 47 92 728 594 613 737 324 382 261 727 244 83 733 288 175 785 34 733 597 128 174 787 446 212 522 367 459 661 366 673 60 273 695 341 234 349 29 212 1 532 391 177 524 413 243 483 321 200 417 4 477 315 373 143 6 474 485 749 353 164 196 465 400 18 330 242 533 212 220 400 400