电瀚
凸包问题
Hank Lv3
  2020-12-23 10:00   2024-01-17 08:00    

问题重述

某大学ACM集训队，不久前向学校申请了一块空地，成为自己的果园。全体队员兴高采烈的策划方案，种植了大批果树，有梨树、桃树、香蕉……后来，发现有些坏蛋，他们暗地里偷摘果园的果子，被ACM集训队队员发现了。因此，大家商量解决办法，有人提出：修筑一圈篱笆，把果园围起来，但是由于我们的经费有限，必须尽量节省资金，所以，我们要找出一种最合理的方案。由于每道篱笆，无论长度多长，都是同等价钱。所以，大家希望设计出来的修筑一圈篱笆的方案所花费的资金最少。有人已经做了准备工序哦，统计了果园里果树的位置，每棵果树分别用二维坐标来表示，进行定位。现在，他们要求根据所有的果树的位置，找出一个n边形的最小篱笆，使得所有果树都包围在篱笆内部，或者在篱笆边沿上。
本题的实质：凸包问题。请使用蛮力法和分治法求解该问题。

问题分析

问题的本质为凸包问题，意图找出一个点集中处于最外围的子点集，使得构成的多边形边数最少。
形式化问题：现有点集，其子集，满足, 且能完全包围.
此处的“完全包围”很难用笼统地用形式化的方式去定义，但我们能在算法的构建过程中的具体分析其数学意义。

算法分析

设计思想

要了解凸包，必须了解凸性的定义。概括来说，平面邻域中任意两点所在的线段上的点都在该邻域中，则该邻域具有凸性。

Divide & Conquer方法

  1. 将所有点按照轴升序排列顺序，最左侧的点和最右侧的点为点集的边界，故一定为凸包上的点。直线 把点集分成了两部分，即 轴上面和下面两部分，分别叫做上包和下包。
    对上包：求距离直线 最远的点 ，即下图中的点。
    Divide & Conquer方法找凸包
  2. 作直线 、，把直线 左侧的点当成是上包，把直线 右侧的点也当成是上包。
  3. 重复上述步骤。
  4. 然后对下包也作如上操作，找出所有凸包的点集。

算法中，排序的复杂度，分治的复杂度为，故算法的复杂度.

Bruce Force方法

两点确定一条直线，如果剩余的其他点都在这条直线的同一侧，则这两个点是凸包上的点，否则就不是。
步骤：

  1. 将点集里面的所有点两两配对，组成 条直线。
  2. 对于每条直线，再检查剩余的 个点是否在直线的同一侧。

    如何判断一个点 是在直线 的左边还是右边呢？（坐标：，，）
    利用叉积求得的面积，当结果为正时，在直线 的上侧；当结果为负时，在直线 的下侧。

时间复杂度：。

Stepping方法

由凸包的定义，对于“所有其他点都在两点构成直线的同一侧”的情况，有这两个点一定是凸包上的两个相邻的或与凸包上另点共线的点的性质。由此观点出发，结合Bruce Force法和Divide & Conquer法种判断是否线上/下有点的方法，引出Stepping算法。
将所有点按照轴升序排列顺序，最左侧的点和最右侧的点为点集的边界，故一定为凸包上的点。
先找出上半部分的凸包：从小到大依次扫描各点，利用叉积公式，判断是否能与点形成的直线，满足“所有其他点都在两点构成直线的同一侧”的情况（即、、点集中另外所有点进行的叉积都小于）。如果满足，则此点为凸包上的与相邻的点（由于是从左到右从小到达有序地查找，故不存在另点共线的情况而在未被发现）。将此点定为，继续重复上面的操作，直到右端点为止。
FD上方无点，是凸包上的点
DA、DC上方有点
DB上方无点，是凸包上的点
BA、BD、BC上方有点
BE上方无点
下方搜索，EA下方无点
然后对线下半部分的点集进行同样操作。找出所有的凸包点集。
理论上，最不理想的情况下，复杂度为.
该方法还可继续优化，在上搜时，除了于左右边界连线上的点（如上图中的点，位于边界的连线上）外，由于有相邻的条件，若某点已经判断不符合凸包点，则在下一次就不需要再判断了；但在下搜时需要再恢复成可判断状态，再进行上述操作。此办法可以降低平均情况下的算法时间。

设计表示

程序结构

凸包问题_程序结构

部分程序框图

Divide & Conquer方法框图

凸包问题_Divide & Conquer 方法程序框图

Bruce Force方法框图

Bruce Force方法程序框图

Stepping方法框图

Stepping方法程序框图

演示

ACM队的篱笆——求凸包 键入x坐标，以空格分离
键入y坐标，以空格分离
           
           
           
运行时间：ms

一些可供使用的样例

1
261 707 186 202 949 83 486 492 881 703 121 950 362 678 521 309 932 384 25 718 921 17 439 366 184 97 790 371 385 572 737 217 563 769 41 421 722 304 141 270 531 430 149 461 435 865 75 524 597 20 804 956 150 203 68 386 304 51 995 993 533 38 512 819 629 498 446 136 881 659 916 735 712 565 142 19 263 567 645 72 772 388 122 250 701 606 884 930 126 175 439 934 386 451 829 205 222 658 802 821 799 865 456 184 958 511 648 868 211 957 887 302 247 82 975 796 276 8 805 524 915 715 980 256 809 646 348 855 769 580 671 969 306 936 401 489 309 583 94 51 315 52 937 868 104 392 497 842 265 983 655 727 291 410 621 461 739 28 448 69 561 740 370 457 184 47 434 182 731 638 893 587 445 234 190 656 595 902 871 39 387 525 168 349 929 455 829 377 408 775 530 830 558 493 797 218 626 925 183 336 519 323 373 878 980 947 70 749 500 828 43 738 939 254 690 734 620 788 932 661 741 354 332 850 752 900 172 456 709 936 968 730 251 417 152 999 412 54 982 607 529 358 219 463 150 7 502 703 963 711 881 657 312 302 689 846 808 217 317 13 144 897 319 834 914 777 810 298 340 343 377 125 222 190 718 570 345 656 281 681 566 695 54 483 919 795 309 796 673 45 513 240 780 138 971 900 716 714 525 244 734 265 828 77 366 29 16 686 650 135 927 884 330 676 716 517 278 983 660 954 512 228 653 810 446 385 162 592 487 272 458 855 670 140 744 840 966 36 412 768 6 114 501 918 521 513 70 38 865 948 261 479 552 728 546 676 298 183 331 354 752 621 219 779 975 669 760 286 137 215 42 22 621 104 987 93 281 586 944 478 69 378 301 538 413 667 801 599 410 501 780 661 720 270 946 79 537 255 926 490 842 975 114 466 716 714 994 47 75 586 283 563 189 692 118 519 604 594 213 145 781 813 379 607 379 797 385 717 395 209 304 245 354 269 990 556 109 956 396 183 796 727 831 819 139 67 414 675 398 67 293 15 850 118 45 142 565 905 772 190 899 755 166 714 814 50 743 357 568 174 917 954 283 940 458 577 571 428 567 744 662 271 370 348 49 98 286 766 17 562 789 109 492 173 52 221 86 495 824 557 689 653 893 22 851 921 317 124 899 567 85 269 328 477 976 79 420 659 399 247 818 455 742 234 887 116 402 218 762 469 992 454 457 969 901 460 253 861 338 264 163 96 370 21 689 428 244 89 905 103 716 10 937 69 821 770 37 913 129 726 985 627 726 859 250 35 359 484 915 547 595 483 995 9 339 514 427 247 215 508 244 268 991 660 18 739 62 820 227 813 743 136 645 3 342 945 719 647 24 270 968 634 485 351 750 442 304 504 400 572 909 716 465 976 770 201 230 130 390 393 921 599 408 522 613 428 242 723 707 322 815 437 61 272 617 412 237 564 107 83 489 954 319 853 843 557 55 420 830 888 781 367 556 391 553 991 888 208 424 30 472 559 587 322 731 818 197 159 457 999 856 905 280 525 976 74 260 223 290 788 299 231 813 337 493 682 630 880 648 322 305 759 70 529 79 955 498 253 770 339 234 998 734 205 499 223 76 642 849 276 770 798 617 207 58 340 513 231 526 207 436 309 702 824 40 838 813 194 606 749 63 505 837 434 168 921 959 105 208 299 966 2 314 928 48 859 178 632 704 898 650 817 58 457 590 347 714 186 274 206 842 623 363 445 984 199 891 604 190 184 865 812 744 986 778 342 110 569 858 459 721 44 479 155 886 0 607 345 968 744 984 354 310 950 100 67 464 17 355 467 635 763 1000 87 955 56 341 99 436 154 634 787 313 753 884 76 349 130 1000 110 900 80 291 482 107 37 893 5 249 338 13 440 186 157 461 578 454 963 40 286 22 652 758 376 614 677 506 847 379 215 376 44 553 946 831 651 675 886 850 383 88 465 313 166 442 793 227 247 423 224 84 683 101 207 264 399 341 447 359 439 188 137 413 866 718 894 767 123 77 370 950 33 326 726 218 137 784 85 681 654 962 943 701 123 453 986 495 46 687 192 223 891 212 382 962 495 347 662 619 945 924 16 314 988 582 645 207 120 96 30 630 713 376 954 925 861 690 739 546 183 377 430 687 298 552 216 430 390 470 646 921 96 691 884 930 304 42 209 42 308 324 739 351 955 863 935 333 378 583 566 678 111 640 798 239 997 192 198 430 252 417 712 80 879 392 411 766 703 667 996 942 509 972 533 235 325 495 291 321 197 2 513 456 136 645 962 572 413 379 367 451 632 928 34 463 530 365 227 490 888 594 783 911 108 905 777 279 964 32 156 43 684 842 829 890 194 112 111 160 670 479 18 306 662 815 704 689 474 885 720 649 247 502 820 28 866 608 313 161 841 946 112 159 482 887 575 186 488 542 331 770 414 661 597 689 355 163 572 645 464 141 908 161 650 635 417 641 524 830 683 286 309 947 345 464 25 975 783 913 710 665 53 795 801 424 701 117 384 565 288 806 147 470 567 153 44 323 942 362 412 713 220 330 449 102 47 436 35 575 516 226 334 11 417 61 355 227 858 841 40 94 922 143 540 316 65 274 14 354 794 951 974 219 898 970 29 358 480 960 65 272 992 67 950 735 220 305 3 425 933 460 874 690 179 798 533 35 724 501 126 206 92 819 14 890 344 561 749 424 214 293 529 459 944 474 805 519 942 108 255 603 140 165 187 878 63 995 499 223 774 159 445 756 223 979 240 864 114 112 316 440 656 344 624 475 542 747 922 314 691 220 560 237 346 53 537 260 503 261 101 595 43 168 534 183 882 660 94 5 819 704 836 422 535 908 458 813 553 63 817 199 155 842 805 334 706 408 326 467 459 759 784 445 395 52 662 542 820 621 525 396 253 452 216 267 908 330 211 146 30 76 194 936 705 218 888 478 875 574 896 642 39 536 396 842 995 866 777 646 757 917 105 266 68 339 677 904 247 241 698 134 174 338 960 405 10 354 913 259 82 617 277 997 425 990 708 522 694 235 308 320 224 949 41 542 273 107 686 701 289 869 500 572 7 549 41 855 773 566 15 709 89 359 922 862 585 184 240 516 975 907 112 573 364 127 71 405 169 16 876 647 527 804 547 812 970 323 514 788 200 563 258 532 691 314 841 5 371 868 835 302 10 723 671 995 695 790 686 184 915 6 52 508 902 975 836 843 611 248 950 96 265 219 724 553 948 389 718 886 514 180 570 713 189 852 714 473 277 665 565 360 319 757 762 332 604 611 112 83 911 950 117 111 594 577 538 648 408 374 685 871 730 92 150 17 883 533 28 9 902 52 511 212 726 796 449 267 6 315 800 359 490 336 58 353 24 556 237 790 843 805 972 695 919 660 752 893 79 705 738 689 653 893 22 851 921 317 124 899 567 85 269 328 477 976 79 420 659 399 247 818 455 742 234 887 116 402 218 762 469 992 454 457 969 901 460 253 861 338 264 163 96 370 21 689 428 244 89 905 103 716 10 937 69 821 770 37 913 129 726 985 627 726 859 250 35 359 484 915 547 595 483 995 9 339 514 427 247 215 508 244 268 991 660 18 739 62 820 227 813 743 136 645 3 342 945 719 647 24 270 968 634 485 351 750 442 304 504 400 572 909 716 465 976 770 201 230 130 390 393 921 599 408 522 613 428 242 723 707 322 815 437 61 272 617 412 237 564 107 83 489 954 319 853 843 557 55 420 830 888 781 367 556 391 553 991 888 208 424 30 472 559 587 322 731 818 197 159 457 999 856 905 280 525 976 74 260 223 290 788 299 231 813 337 493 682 630 880 648 322 305 759 70 529 79 955 498 253 770 339 234 998 734 205 499 223 76 642 849 276 770 798 617 207 58 340 513 231 526 207 436 309 702 824 40 838 813 194 606 749 63 505 837 434 168 921 959 105 208 299 966 2 314 928 48 859 178 632 704 898 650 817 58 457 590 347 714 186 274 206 842 623 363 445 984 199 891 604 190 184 865 812 744 986 778 342 110 569 858 459 721 44 479 155 886 0 607 345 968 744 984 354 310 950 100 67 464 17 355 467 635 763 1000 87 955 56 341 99 436 154 634 787 313 753 884 76 349 130 1000 110 900 80 291 482 107 37 893 5 249 338 13 440 186 157 461 578 454 963 40 286 22 652 758 376 614 677 506 847 379 215 376 44 553 946 831 651 675 886 850 383 88 465 313 166 442 793 227 247 423 224 84 683 101 207 264 399 341 447 359 439 188 137 413 866 718 894 767 123 77 370 950 33 326 726 218 137 784 85 681 654 962 943 701 123 453 986 495 46 687 192 223 891 212 382 962 495 347 662 619 945 924 16 314 988 582 645 207 120 96 30 630 713 376 954 925 861 690 739 546 183 377 430 687 298 552 216 430 390 470 646 921 96 691 884 930 304 42 209 42 308 324 739 351 955 863 935 333 378 583 566 678 111 640 798 239 997 192 198 430 252 417 712 80 879 392 411 766 703 667 996 942 509 972 533 235 325 495 291 321 197 857 352 333 866 266 567 99 240 794 937 892 57 468 762 567 564 957 942 788 5 272 981 38 618 944 465 91 313 131 451 392 730 13 976 431 144 205 123 410 869 213 27 213 156 566 386 983 982 937 934 800 353 454 489 2 404 695 147 922 482 999 341 816 470 466 619 182 323 905 105 305 359 369 324 391 587 24 921 508 493 272 432 859 917 821 596 243 63 444 306 439 4 109 341 867 550 828 125 596 944 723 960 892 662 559 174 714 188 808 909 529 532 324 382 787 299 569 784 755 562 179 514 595 757 21 96 308 967 701 100 64 982 987 399 165 855 445 829 93 255 412 473 612 564 969 942 473 394 687 724 711 702 738 769 853 486 422 849 408 132 896 240 659 915 431 166 731 179 269 367 662 254 94 642 306 575 401 483 921 508 100 590 735 511 415 457 613 47 398 271 850 72 653 663 249 775 971 874 955 483 521 421 279 185 397 921 856 915 169 801 589 849 451 554 106 336 895 397 924 257 999 372 483 810 826 978 799 483 368 640 69 407 67 944 717 542 598 121 625 775 693 829 399 323 985 288 48 82 53 406 182 321 400 441 551 171 578 12 856 875 920 966 419 730 894 728 783 249 541 315 925 22 739 667 418 33 83 698 916 408 739 191 331 799 574 817 811 931 843 755 318 309 63 472 747 193 160 30 784 264 860 206 221 343 923 338 321 991 337 480 524 960 683 636 763 636 523 724 39 387 258 722 178 621 599 82 7 842 919 555 75 851 827 18 181 346 841 921 964 191 257 632 704 345 496 752 721 271 640 724 247 905 321 582 832 56 951 55 952 235 554 718 991 7 28 34 470 110 813 661 857 42 968 550 80 346 525 350 469 212 331 46 980 689 945 214 981 977 156 894 837 239 145 572 755 700 472 421 958 552 207 748 231 372 432 540 709 148 885 990 470 214 998 873 642 409 509 500 303 835 631 723 951 768 796 77 834 680 616 796 114 179 369 732 421 146 238 175 721 533 360 599 683 354 375 266 187 978 595 297 665 599 386 309 46 684 979 440 722 859 110 587 153 829 691 105 715 711 957 401 748 16 635 588 832 824 148 668 952 34 558 752 698 382 503 30 437 300 554 809 132 562 728 941 170 199 895 922 889 940 926 487 99 228 812 390 605 407 889 877 611 354 132 82 748 688 544 406 393 741 252 568 339 850 190 92 813 706 313 966 841 60 351 484 898 641 972 398 231 170 457 956 427 97 590 803 563 402 646 844 860 241 351 927 665 225 181 532 504 99 868 888 372 650 187 5 360 516 279 364 230 689 991 915 371 815 715 67 612 691 586 365 353 562 233 873 967 761 936 660 376 321 829 955 672 517 152 737 917 917 293 96 650 758 497 267 949 785 733 888 305 740 10 117 282 449 398 628 955 797 264 697 810 762 241 285 875 174 868 743 364 897 534 897 407 140 671 459 427 635 358 862 457 959 984 143 175 904 590 394 363 571 327 37 480 510 299 423 488 651 515 287 210 490 241 352 164 351 923 878 77 877 602 988 812 783 146 622 743 298 197 82 386 101 837 942 100 22 886 585 630 78 869 327 38 13 835 832 890 413 974 157 976 325 445 165 993 104 601 350 469 549 248 539 455 620 531 53 745 164 420 945 112 668 972 307 178 681 446 40 331 940 805 616 275 868 509 195 535 145 605 461 937 382 467 394 396 978 461 181 977 255 133 129 470 472 220 814 76 351 337 660 497 931 938 965 466 256 529 551 296 179 846 555 334 300 199 9 547 893 605 381 551 847 217 923 902 549 173 613 733 912 927 866 975 95 344 562 15 798 661 610 693 606 928 371 167 221 658 156 266 753 943 130 968 275 816 972 767 398 439 442 205 401 732 733 421 34 481 47 512 269 803 275 934 935 676 182 569 200 494 383 836 146 30 890 996 369 728 296 298 858 111 796 148 12 61 743 8 20 980 506 877 949 516 967 536 598 346 849 70 755 477 712 593 112 101 612 464 927 290 77 951 313 933 616 115 555 415 895 637 182 621 741 917 787 904 430 630 770 99 814 896 533 173 376 660 615 225 593 65 318 704 343 724 781 567 857 15 522 692 151 158 499 185 839 514 106 70 423 866 856 409 55 339 586 585 835 174 41 356 477 902 65 653 922 637 710 406 628 677 321 879 981 595 37 328 636 424 951 633 192 960 593 261 735 122 208 360 837 224 848 680 661 486 24 157 602 495 68 204 319 737 50 604 830 103 14 549 71 840 241 32 253 600 738 438 245 717 517
1
689 653 893 22 851 921 317 124 899 567 85 269 328 477 976 79 420 659 399 247 818 455 742 234 887 116 402 218 762 469 992 454 457 969 901 460 253 861 338 264 163 96 370 21 689 428 244 89 905 103 716 10 937 69 821 770 37 913 129 726 985 627 726 859 250 35 359 484 915 547 595 483 995 9 339 514 427 247 215 508 244 268 991 660 18 739 62 820 227 813 743 136 645 3 342 945 719 647 24 270 968 634 485 351 750 442 304 504 400 572 909 716 465 976 770 201 230 130 390 393 921 599 408 522 613 428 242 723 707 322 815 437 61 272 617 412 237 564 107 83 489 954 319 853 843 557 55 420 830 888 781 367 556 391 553 991 888 208 424 30 472 559 587 322 731 818 197 159 457 999 856 905 280 525 976 74 260 223 290 788 299 231 813 337 493 682 630 880 648 322 305 759 70 529 79 955 498 253 770 339 234 998 734 205 499 223 76 642 849 276 770 798 617 207 58 340 513 231 526 207 436 309 702 824 40 838 813 194 606 749 63 505 837 434 168 921 959 105 208 299 966 2 314 928 48 859 178 632 704 898 650 817 58 457 590 347 714 186 274 206 842 623 363 445 984 199 891 604 190 184 865 812 744 986 778 342 110 569 858 459 721 44 479 155 886 0 607 345 968 744 984 354 310 950 100 67 464 17 355 467 635 763 1000 87 955 56 341 99 436 154 634 787 313 753 884 76 349 130 1000 110 900 80 291 482 107 37 893 5 249 338 13 440 186 157 461 578 454 963 40 286 22 652 758 376 614 677 506 847 379 215 376 44 553 946 831 651 675 886 850 383 88 465 313 166 442 793 227 247 423 224 84 683 101 207 264 399 341 447 359 439 188 137 413 866 718 894 767 123 77 370 950 33 326 726 218 137 784 85 681 654 962 943 701 123 453 986 495 46 687 192 223 891 212 382 962 495 347 662 619 945 924 16 314 988 582 645 207 120 96 30 630 713 376 954 925 861 690 739 546 183 377 430 687 298 552 216 430 390 470 646 921 96 691 884 930 304 42 209 42 308 324 739 351 955 863 935 333 378 583 566 678 111 640 798 239 997 192 198 430 252 417 712 80 879 392 411 766 703 667 996 942 509 972 533 235 325 495 291 321 197 857 352 333 866 266 567 99 240 794 937 892 57 468 762 567 564 957 942 788 5 272 981 38 618 944 465 91 313 131 451 392 730 13 976 431 144 205 123 410 869 213 27 213 156 566 386 983 982 937 934 800 353 454 489 2 404 695 147 922 482 999 341 816 470 466 619 182 323 905 105 305 359 369 324 391 587 24 921 508 493 272 432 859 917 821 596 243 63 444 306 439 4 109 341 867 550 828 125 596 944 723 960 892 662 559 174 714 188 808 909 529 532 324 382 787 299 569 784 755 562 179 514 595 757 21 96 308 967 701 100 64 982 987 399 165 855 445 829 93 255 412 473 612 564 969 942 473 394 687 724 711 702 738 769 853 486 422 849 408 132 896 240 659 915 431 166 731 179 269 367 662 254 94 642 306 575 401 483 921 508 100 590 735 511 415 457 613 47 398 271 850 72 653 663 249 775 971 874 955 483 521 421 279 185 397 921 856 915 169 801 589 849 451 554 106 336 895 397 924 257 999 372 483 810 826 978 799 483 368 640 69 407 67 944 717 542 598 121 625 775 693 829 399 323 985 288 48 82 53 406 182 321 400 441 551 171 578 12 856 875 920 966 419 730 894 728 783 249 541 315 925 22 739 667 418 33 83 698 916 408 739 191 331 799 574 817 811 931 843 755 318 309 63 472 747 193 160 30 784 264 860 206 221 343 923 338 321 991 337 480 524 960 683 636 763 636 523 724 39 387 258 722 178 621 599 82 7 842 919 555 75 851 827 18 181 346 841 921 964 191 257 632 704 345 496 752 721 271 640 724 247 905 321 582 832 56 951 55 952 235 554 718 991 7 28 34 470 110 813 661 857 42 968 550 80 346 525 350 469 212 331 46 980 689 945 214 981 977 156 894 837 239 145 572 755 700 472 421 958 552 207 748 231 372 432 540 709 148 885 990 470 214 998 873 642 409 509 500 303 835 631 723 951 768 796 77 834 680 616 796 114 179 369 732 421 146 238 175 721 533 360 599 683 354 375 266 187 978 595 297 665 599 386 309 46 684 979 440 722 859 110 587 153 829 691 105 715 711 957 401 748 16 635 588 832 824 148 668 952 34 558 752 698 382 503 30 437 300 554 809 132 562 728 941 170 199 895 922 889 940 926 487 99 228 812 390 605 407 889 877 611 354 132 82 748 688 544 406 393 741 252 568 339 850 190 92 813 706 313 966 841 60 351 484 898 641 972 398 231 170 457 956 427 97 590 803 563 402 646 844 860 241 351 927 665 225 181 532 504 99 868 888 372 650 187 5 360 516 279 364 230 689 991 915 371 815 715 67 612 691 586 365 353 562 233 873 967 761 936 660 376 321 829 955 672 517 152 737 917 917 293 96 650 758 497 267 949 785 733 888 305 740 10 117 282 449 398 628 955 797 264 697 810 762 241 285 875 174 868 743 364 897 534 897 407 140 671 459 427 635 358 862 457 959 984 143 175 904 590 394 363 571 327 37 480 510 299 423 488 651 515 287 210 490 241 352 164 351 923 878 77 877 602 988 812 783 146 622 743 298 197 82 386 101 837 942 100 22 886 585 630 78 869 327 38 13 835 832 890 413 974 157 976 325 445 165 993 104 601 350 469 549 248 539 455 620 531 53 745 164 420 945 112 668 972 307 178 681 446 40 331 940 805 616 275 868 509 195 535 145 605 461 937 382 467 394 396 978 461 181 977 255 133 129 470 472 220 814 76 351 337 660 497 931 938 965 466 256 529 551 296 179 846 555 334 300 199 9 547 893 605 381 551 847 217 923 902 549 173 613 733 912 927 866 975 95 344 562 15 798 661 610 693 606 928 371 167 221 658 156 266 753 943 130 968 275 816 972 767 398 439 442 205 401 732 733 421 34 481 47 512 269 803 275 934 935 676 182 569 200 494 383 836 146 30 890 996 369 728 296 298 858 111 796 148 12 61 743 8 20 980 506 877 949 516 967 536 598 346 849 70 755 477 712 593 112 101 612 464 927 290 77 951 313 933 616 115 555 415 895 637 182 621 741 917 787 904 430 630 770 99 814 896 533 173 376 660 615 225 593 65 318 704 343 724 781 567 857 15 522 692 151 158 499 185 839 514 106 70 423 866 856 409 55 339 586 585 835 174 41 356 477 902 65 653 922 637 710 406 628 677 321 879 981 595 37 328 636 424 951 633 192 960 593 261 735 122 208 360 837 224 848 680 661 486 24 157 602 495 68 204 319 737 50 604 830 103 14 549 71 840 241 32 253 600 738 438 245 717 517 261 707 186 202 949 83 486 492 881 703 121 950 362 678 521 309 932 384 25 718 921 17 439 366 184 97 790 371 385 572 737 217 563 769 41 421 722 304 141 270 531 430 149 461 435 865 75 524 597 20 804 956 150 203 68 386 304 51 995 993 533 38 512 819 629 498 446 136 881 659 916 735 712 565 142 19 263 567 645 72 772 388 122 250 701 606 884 930 126 175 439 934 386 451 829 205 222 658 802 821 799 865 456 184 958 511 648 868 211 957 887 302 247 82 975 796 276 8 805 524 915 715 980 256 809 646 348 855 769 580 671 969 306 936 401 489 309 583 94 51 315 52 937 868 104 392 497 842 265 983 655 727 291 410 621 461 739 28 448 69 561 740 370 457 184 47 434 182 731 638 893 587 445 234 190 656 595 902 871 39 387 525 168 349 929 455 829 377 408 775 530 830 558 493 797 218 626 925 183 336 519 323 373 878 980 947 70 749 500 828 43 738 939 254 690 734 620 788 932 661 741 354 332 850 752 900 172 456 709 936 968 730 251 417 152 999 412 54 982 607 529 358 219 463 150 7 502 703 963 711 881 657 312 302 689 846 808 217 317 13 144 897 319 834 914 777 810 298 340 343 377 125 222 190 718 570 345 656 281 681 566 695 54 483 919 795 309 796 673 45 513 240 780 138 971 900 716 714 525 244 734 265 828 77 366 29 16 686 650 135 927 884 330 676 716 517 278 983 660 954 512 228 653 810 446 385 162 592 487 272 458 855 670 140 744 840 966 36 412 768 6 114 501 918 521 513 70 38 865 948 261 479 552 728 546 676 298 183 331 354 752 621 219 779 975 669 760 286 137 215 42 22 621 104 987 93 281 586 944 478 69 378 301 538 413 667 801 599 410 501 780 661 720 270 946 79 537 255 926 490 842 975 114 466 716 714 994 47 75 586 283 563 189 692 118 519 604 594 213 145 781 813 379 607 379 797 385 717 395 209 304 245 354 269 990 556 109 956 396 183 796 727 831 819 139 67 414 675 398 67 293 15 850 118 45 142 565 905 772 190 899 755 166 714 814 50 743 357 568 174 917 954 283 940 458 577 571 428 567 744 662 271 370 348 49 98 286 766 17 562 789 109 492 173 52 221 86 495 824 557 689 653 893 22 851 921 317 124 899 567 85 269 328 477 976 79 420 659 399 247 818 455 742 234 887 116 402 218 762 469 992 454 457 969 901 460 253 861 338 264 163 96 370 21 689 428 244 89 905 103 716 10 937 69 821 770 37 913 129 726 985 627 726 859 250 35 359 484 915 547 595 483 995 9 339 514 427 247 215 508 244 268 991 660 18 739 62 820 227 813 743 136 645 3 342 945 719 647 24 270 968 634 485 351 750 442 304 504 400 572 909 716 465 976 770 201 230 130 390 393 921 599 408 522 613 428 242 723 707 322 815 437 61 272 617 412 237 564 107 83 489 954 319 853 843 557 55 420 830 888 781 367 556 391 553 991 888 208 424 30 472 559 587 322 731 818 197 159 457 999 856 905 280 525 976 74 260 223 290 788 299 231 813 337 493 682 630 880 648 322 305 759 70 529 79 955 498 253 770 339 234 998 734 205 499 223 76 642 849 276 770 798 617 207 58 340 513 231 526 207 436 309 702 824 40 838 813 194 606 749 63 505 837 434 168 921 959 105 208 299 966 2 314 928 48 859 178 632 704 898 650 817 58 457 590 347 714 186 274 206 842 623 363 445 984 199 891 604 190 184 865 812 744 986 778 342 110 569 858 459 721 44 479 155 886 0 607 345 968 744 984 354 310 950 100 67 464 17 355 467 635 763 1000 87 955 56 341 99 436 154 634 787 313 753 884 76 349 130 1000 110 900 80 291 482 107 37 893 5 249 338 13 440 186 157 461 578 454 963 40 286 22 652 758 376 614 677 506 847 379 215 376 44 553 946 831 651 675 886 850 383 88 465 313 166 442 793 227 247 423 224 84 683 101 207 264 399 341 447 359 439 188 137 413 866 718 894 767 123 77 370 950 33 326 726 218 137 784 85 681 654 962 943 701 123 453 986 495 46 687 192 223 891 212 382 962 495 347 662 619 945 924 16 314 988 582 645 207 120 96 30 630 713 376 954 925 861 690 739 546 183 377 430 687 298 552 216 430 390 470 646 921 96 691 884 930 304 42 209 42 308 324 739 351 955 863 935 333 378 583 566 678 111 640 798 239 997 192 198 430 252 417 712 80 879 392 411 766 703 667 996 942 509 972 533 235 325 495 291 321 197 2 513 456 136 645 962 572 413 379 367 451 632 928 34 463 530 365 227 490 888 594 783 911 108 905 777 279 964 32 156 43 684 842 829 890 194 112 111 160 670 479 18 306 662 815 704 689 474 885 720 649 247 502 820 28 866 608 313 161 841 946 112 159 482 887 575 186 488 542 331 770 414 661 597 689 355 163 572 645 464 141 908 161 650 635 417 641 524 830 683 286 309 947 345 464 25 975 783 913 710 665 53 795 801 424 701 117 384 565 288 806 147 470 567 153 44 323 942 362 412 713 220 330 449 102 47 436 35 575 516 226 334 11 417 61 355 227 858 841 40 94 922 143 540 316 65 274 14 354 794 951 974 219 898 970 29 358 480 960 65 272 992 67 950 735 220 305 3 425 933 460 874 690 179 798 533 35 724 501 126 206 92 819 14 890 344 561 749 424 214 293 529 459 944 474 805 519 942 108 255 603 140 165 187 878 63 995 499 223 774 159 445 756 223 979 240 864 114 112 316 440 656 344 624 475 542 747 922 314 691 220 560 237 346 53 537 260 503 261 101 595 43 168 534 183 882 660 94 5 819 704 836 422 535 908 458 813 553 63 817 199 155 842 805 334 706 408 326 467 459 759 784 445 395 52 662 542 820 621 525 396 253 452 216 267 908 330 211 146 30 76 194 936 705 218 888 478 875 574 896 642 39 536 396 842 995 866 777 646 757 917 105 266 68 339 677 904 247 241 698 134 174 338 960 405 10 354 913 259 82 617 277 997 425 990 708 522 694 235 308 320 224 949 41 542 273 107 686 701 289 869 500 572 7 549 41 855 773 566 15 709 89 359 922 862 585 184 240 516 975 907 112 573 364 127 71 405 169 16 876 647 527 804 547 812 970 323 514 788 200 563 258 532 691 314 841 5 371 868 835 302 10 723 671 995 695 790 686 184 915 6 52 508 902 975 836 843 611 248 950 96 265 219 724 553 948 389 718 886 514 180 570 713 189 852 714 473 277 665 565 360 319 757 762 332 604 611 112 83 911 950 117 111 594 577 538 648 408 374 685 871 730 92 150 17 883 533 28 9 902 52 511 212 726 796 449 267 6 315 800 359 490 336 58 353 24 556 237 790 843 805 972 695 919 660 752 893 79 705 738

源代码

JavaScript

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
<script src="https://jsd.cdn.zzko.cn/npm/chart.js@2.9.4"></script>
var n=0
var s = new Array()
var ans = new Array()

function cmp(a,b)
{
    return a.x - b.x
}

function area(a,b,i)
{
    return (s[b].x-s[a].x)*(s[i].y-s[a].y)-(s[b].y-s[a].y)*(s[i].x-s[a].x)
}

function search_bf()
{
    var i,a,b,max_area,min_area;
    for(a=0;a<n-1;a++)
    {
        for(b=a+1;b<n;b++)
        {
            max_area=0;
            min_area=0;
            for(i=0;i<n;i++)
            {
                if(area(a,b,i)>max_area)
                {
                    max_area=area(a,b,i);
                }
                if(area(a,b,i)<min_area)
                {
                    min_area=area(a,b,i);
                }
            }
            if(max_area == 0 || min_area == 0)
            {
                s[a].ch=true;
                s[b].ch=true;
            }
        }
    }
}

function search_se(a,b,direction)
{
    //若向量叉乘为负,说明点在直线下面,否则在直线上面(参照直线方向为从左到右)
    //a为左起点，b为右终点。
    //★★★★凸包的相邻两个点之间上/下一定是没有点的
    //从a到b的每个点i，看上一个凸包点与i的上/下方是否有其余的点
    //    具体是能否构成三角形(即只要area(上一个凸包点,i,j)不为0 就构成)
    //	  不能构成就证明i是边界
    //如果没有就证明是边界。加入ch.
    var i, j, max_area=0, c = 0,last_ch=0;
    var flag;
    for(i=a+1;i<b;i++)
    {
        flag=true;
//        底边上方的只搜上 底边下方的只搜下
//        点在底边边上的则都要搜
        if((!direction && area(a,b,i)>0) || (direction && area(a,b,i)<0) )
            continue;
        // 此处没有“最大距离”的前提，必须从0开始搜索
        for(j=0;j<n;j++)
        {
            // 如果dir为真，说明在上方搜索，面积为正，
            // 如果dir为假，说明在下方搜索，面积为负
            if((direction && area(last_ch,i,j)>0) || (!direction && area(last_ch,i,j)<0))
            {
                flag = false;
                break;
            }
        }
//      如果验证是上下没有点
        if(flag)
        {
            s[i].ch=true;
            last_ch = i;
        }
    }
}

function search_dc(a,b,direction)
{
    var i, max_area, c=null
    max_area = 0
    // 找出距离直线最远的点 
    for(i=a+1;i<b;i++)
    {
        // 如果dir为真，说明在上方搜索，面积为正，
        // 如果dir为假，说明在下方搜索，面积为负
        // 如果刚好有点面积为零，且没有更大或更小，会使得c有值而max_area为0
            // 这个点就刚好和边缘共线，因此也加入到ch中 
        if((direction && area(a,b,i)>=max_area) || (!direction && area(a,b,i)<=max_area))
        {
            max_area = area(a,b,i)
            c = i
        }
    }
    // 直线上/下方仍有点 
    if(c)
    {
        // 该点一定是凸包边缘
        s[c].ch = true
        // 继续沿着当前方向分治深搜
        search_dc(a,c,direction)
        search_dc(c,b,direction)
    }
    return 0
}

function timer(start)
{
    if(start)
        starttime = new Date().getTime()
    endtime = new Date().getTime()
    return endtime-starttime
}

function init(sort)
{
    timer(true)
    if(sort)
        s.sort(cmp)
    s[0].ch = true
    s[n-1].ch = true
}

function input()
{
    var x = document.getElementById('points_x').value
    var y = document.getElementById('points_y').value
    x = x.split(' ').map(Number)
    y = y.split(' ').map(Number)
    if(x.length != y.length)
    {
        alert('x 和 y 不对应，数目不同。')
        return false
    }
    else
    {
        n=x.length
        x.map((cur,index)=>{
            s.push({
                'x': x[index],
                'y': y[index],
                'ch': false,
            })
        })
        return true
    }
}

function output()
{
    for(var i=0;i<n;i++)
    {
        //逆时针输出,先输出下半包
        if(s[i].ch && area(0,n-1,i)<=0)
            ans.push({
                x: s[i].x,
                y: s[i].y
            })
    }
    for(var i=n-1;i>=0;i--)
    {
        if(s[i].ch && area(0,n-1,i)>0)
            ans.push({
                    x: s[i].x,
                    y: s[i].y
                })
    }
    document.getElementById("rt").innerHTML = timer(false)
    // var ctx = document.getElementById("myChart").getContext('2d');
    var scatterChart = new Chart(ctx,
    {
        type: "scatter",
        data:
        {
            datasets:
            [
                {
                    label: "原数据",
                    borderColor: "rgb(30,144,255)",
                    data: s,
                    pointBackgroundColor: "rgb(30,144,255)",
                    pointRadius: 8,
                    pointHoverRadius: 20,
                },
                {
                    label: "凸包数据",
                    borderColor: "rgb(255, 99, 132)",
                    data: ans,
                    pointBackgroundColor: "rgb(255, 99, 132)",
                    pointRadius: 15,
                    pointHoverRadius: 20,
                }
            ]
        },
    });
}

function clean()
{
    s = new Array()
    ans = new Array()
    n=0
}

document.getElementById('submit_dc').onclick = function(event)
{
    clean()
    input()
    init(true)
    search_dc(0,n-1,true)
    search_dc(0,n-1,false)
    output()
}

document.getElementById('submit_se').onclick = function(event)
{
    
    clean()
    input()
    init(true)
    search_se(0,n-1,true)
    search_se(0,n-1,false)
    output()
}

document.getElementById('submit_bf').onclick = function(event)
{
    timer(true)
    clean()
    input()
    search_bf()
    search_bf()
    output()
}

C语言

D&C

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>
#include<algorithm>
using namespace std;

struct Point
{
    int x;
    int y;
    bool ch;
}s[105];
int n;

int cmp(Point &a,Point &b)
{
	return a.x < b.x;
}

//求三角形面积
int area(int a,int b, int i)
{
    return (s[b].x-s[a].x)*(s[i].y-s[a].y)-(s[b].y-s[a].y)*(s[i].x-s[a].x);
}


/*若向量叉乘为负,说明点在直线下面,否则在直线上面(参照直线方向为从左到右)*/
int search(int a,int b,bool direction)
{
    int i, max_area, c = 0;
    max_area = 0;
    // 找出距离直线最远的点
	// 第一轮搜索已经将最高地点找出，此后再的斜边斜率一定k>=0，
	// 也就不可能再有比线更高的点，所以可以限制搜索范围
    for(i=a+1;i<b;i++)
    {
        // 如果dir为真，说明在上方搜索，面积为正，
        // 如果dir为假，说明在下方搜索，面积为负
        // 如果刚好有点面积为零，且没有绝对面积更大的点，会使得c有值而max_area为0
            // 这个点就刚好和边缘共线，因此也加入到ch中
			//意味着只要有c就要加入
        if((direction && area(a,b,i)>=max_area) || (!direction && area(a,b,i)<=max_area))
        {
            max_area = area(a,b,i);
            c = i;
        }
    }
    // 直线上/下方仍有点
    if(c)
    {
        // 该点一定是凸包
        s[c].ch = true;
        // 继续沿着当前方向分治深搜
        search(a,c,direction);
        search(c,b,direction);
    }
    return 0;
}

int in()
{
	scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d", &s[i].x, &s[i].y);
		s[i].ch = false;
    }
    return 0;
}
int out()
{
	for(int i=0;i<n;i++)
    {
		//逆时针输出,先输出下半包
        if(s[i].ch && area(0,n-1,i)<=0)
            printf("%d,%d\n", s[i].x, s[i].y);
    }
    for(int i=n-1;i>=0;i--)
    {
		if(s[i].ch && area(0,n-1,i)>0)
			printf("%d,%d\n", s[i].x, s[i].y);
	}
	return 0;
}
int init()
{
    sort(s,s+n,cmp);
	s[0].ch = true;
    s[n-1].ch = true;
    return 0;
}
int main()
{
	in();
	init();
    search(0, n-1, true); // 上搜
    search(0, n-1, false); // 下搜
    out();
    return 0;
}

BF

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
using namespace std;

struct Point
{
    int x;
    int y;
    bool ch;
}s[105];
int n;

//求三角形面积
int area(int a,int b, int i)
{
    return (s[b].x-s[a].x)*(s[i].y-s[a].y)-(s[b].y-s[a].y)*(s[i].x-s[a].x);
}

int search()
{
	int i,a,b,max_area,min_area;
	for(a=0;a<n-1;a++)
	{
		for(b=a+1;b<n;b++)
		{
			max_area=0;
			min_area=0;
			for(i=0;i<n;i++)
			{
				if(area(a,b,i)>max_area)
				{
					max_area=area(a,b,i);
				}
				if(area(a,b,i)<min_area)
				{
					min_area=area(a,b,i);
				}
			}
			if(max_area == 0 || min_area == 0)
			{
				s[a].ch=true;
				s[b].ch=true;
			}
		}
	}
    return 0;
}

int in()
{
	scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d", &s[i].x, &s[i].y);
		s[i].ch = false;
    }
    return 0;
}
int out()
{
	for(int i=0;i<n;i++)
    {
        if(s[i].ch)
            printf("%d,%d\n", s[i].x, s[i].y);
    }
}
int main()
{
	in();
    search();
    out();
    return 0;
}

Se

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<algorithm>
using namespace std;

struct Point
{
    int x;
    int y;
    bool ch;
}s[105];
int n;

int cmp(Point &a,Point &b)
{
	return a.x < b.x;
}

//求三角形面积
int area(int a,int b, int i)
{
    return (s[b].x-s[a].x)*(s[i].y-s[a].y)-(s[b].y-s[a].y)*(s[i].x-s[a].x);
}


//若向量叉乘为负,说明点在直线下面,否则在直线上面(参照直线方向为从左到右)
//a为左起点，b为右终点。
//★★★★凸包的相邻两个点之间上/下一定是没有点的
//从a到b的每个点i，看上一个凸包点与i的上/下方是否有其余的点
//    具体是能否构成三角形(即只要area(上一个凸包点,i,j)不为0 就构成)
//	  不能构成就证明i是边界
//如果没有就证明是边界。加入ch.
int search(int a,int b,bool direction)
{
    int i, j, max_area=0, c = 0,last_ch=0;
	bool flag;
	for(i=a+1;i<b;i++)
	{
		flag=true;
//        横线上的只搜上 横线下的只搜下
//        点在线上的都要搜
		if((!direction && area(a,b,i)>0) || (direction && area(a,b,i)<0) )
			continue;
		// 此处没有“最大距离”的前提，必须从0开始搜索
		for(j=0;j<n;j++)
		{
			// 如果dir为真，说明在上方搜索，面积为正，
		    // 如果dir为假，说明在下方搜索，面积为负
			if((direction && area(last_ch,i,j)>0) || (!direction && area(last_ch,i,j)<0))
	        {
				flag = false;
	            break;
	        }
		}
//      如果验证是上下没有点
		if(flag)
		{
			s[i].ch=true;
			last_ch = i;
		}
	}
    return 0;
}

int in()
{
	scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d", &s[i].x, &s[i].y);
		s[i].ch = false;
    }
    return 0;
}
int out()
{
	for(int i=0;i<n;i++)
    {
		//逆时针输出,先输出下半包
        if(s[i].ch && area(0,n-1,i)<=0)
            printf("%d,%d\n", s[i].x, s[i].y);
    }
    for(int i=n-1;i>=0;i--)
    {
		if(s[i].ch && area(0,n-1,i)>0)
			printf("%d,%d\n", s[i].x, s[i].y);
	}
	return 0;
}
int init()
{
    sort(s,s+n,cmp);
	s[0].ch = true;
    s[n-1].ch = true;
    return 0;
}
int main()
{
	in();
	init();
    search(0, n-1, true); // 上搜
    search(0, n-1, false); // 下搜
    out();
    return 0;
}

心得体会

凸包问题本身并不困难，关键在于能不能够做到思想迁移，也就是举一反三的能力。
在了解了分治算法后，我一直在想如何将其迁移到凸包上。我原以为将点集一分为二，再一分为二……问题在于“分”了后该如何“治”？想了很久也没有所以然，只好在网络上搜索教学PPT。原来是利用凸包的性质，找出边集，继续深度分治就可以了，这我才了解，D&C算法还要结合问题本身的性质来一起思考。
在写完凸包的D&C算法后，我又开始思考如何使用其他方法来解决问题。我原本考虑的是将所有的点集共个找出，再一个个验证，但这样其实复杂度太大。我便从分治学到的“结合凸包的性质”入手，发现凸包上相邻两个点一定只有一边有点，而且边集的上方的只有下方有点，边集的下方的只有上方有点。从这里说开去，推出了“Stepping方法”。

知识交汇点：此方法实质为Jarvis方法。本质上是通过对“凸包性质”的判断而产生的。

我先使用最熟悉的C语言和C++编写程序，然后迁移再到JavaScript上，并利用图形可视化了算法的结果，不仅锻炼了我编写JavaScript的能力，还学会了Chart.js图形库。
总之，这次课程设计丰富了我的计算几何、JavaScript，特别是算法设计知识。在设计过程中，感谢在我弄错课题时邬思奇老师的理解宽容，感谢各位老师的帮助支援。大家的助力是我完成本次课程设计所不可或缺的力量。

 评论
评论插件加载失败
正在加载评论插件
  1. 1. 问题重述
  2. 2. 问题分析
  3. 3. 算法分析
    1. 3.1. 设计思想
      1. 3.1.1. Divide & Conquer方法
      2. 3.1.2. Bruce Force方法
      3. 3.1.3. Stepping方法
    2. 3.2. 设计表示
      1. 3.2.1. 程序结构
      2. 3.2.2. 部分程序框图
        1. 3.2.2.1. Divide & Conquer方法框图
        2. 3.2.2.2. Bruce Force方法框图
        3. 3.2.2.3. Stepping方法框图
  4. 4. 演示
    1. 4.1. 一些可供使用的样例
  5. 5. 源代码
    1. 5.1. JavaScript
    2. 5.2. C语言
      1. 5.2.1. D&C
      2. 5.2.2. BF
      3. 5.2.3. Se
  6. 6. 心得体会
© 2020 - 2024    Hank
由 Hexo 驱动 & 主题 Keep
本站由 提供部署服务
访客数 访问量
  1. 1. 问题重述
  2. 2. 问题分析
  3. 3. 算法分析
    1. 3.1. 设计思想
      1. 3.1.1. Divide & Conquer方法
      2. 3.1.2. Bruce Force方法
      3. 3.1.3. Stepping方法
    2. 3.2. 设计表示
      1. 3.2.1. 程序结构
      2. 3.2.2. 部分程序框图
        1. 3.2.2.1. Divide & Conquer方法框图
        2. 3.2.2.2. Bruce Force方法框图
        3. 3.2.2.3. Stepping方法框图
  4. 4. 演示
    1. 4.1. 一些可供使用的样例
  5. 5. 源代码
    1. 5.1. JavaScript
    2. 5.2. C语言
      1. 5.2.1. D&C
      2. 5.2.2. BF
      3. 5.2.3. Se
  6. 6. 心得体会