|
|
back to boardDiscussion of Problem 1185. WallDamn, simple algo but WA#9! Help, please. Posted by Alexey 9 Aug 2006 14:45 Type Rec=Record x,y:real; End; Var a:array[0..1001] of Rec; n,l:integer; la,i:integer; Procedure Input; Var t:Rec; i:integer; Function Check:boolean; Begin Check:=(a[la].x-a[la-1].x)*(t.y-a[la-1].y)-(t.x-a[la-1].x)*(a[la].y-a[la-1].y)>=0; End; Begin Readln(n,l); Readln(a[1].x,a[1].y); Readln(a[2].x,a[2].y); Readln(a[3].x,a[3].y); la:=3; For i:=4 to n do Begin Readln(t.x,t.y); While (la>1) and Check do dec(la); inc(la); a[la]:=t; End; End; Function Calc:real; Var i:integer; t:real; Begin a[la+1]:=a[1]; t:=0; For i:=1 to la do t:=t+sqrt(sqr(a[i].x-a[i+1].x)+sqr(a[i].y-a[i+1].y)); Calc:=(t)+2*pi*l; End; Procedure Output; Begin Writeln(Calc:0:0); End; BEGIN Input; Output; END. Thanks. Re: Damn, simple algo but WA#9! Help, please. I get WA #9, too :( Re: Damn, simple algo but WA#9! Help, please. I think you forgot two things - first is that the first point may not be a part of a convex hull and you always have the first point in your list and second is that you don't check if the last point is a part of a convex hull. Re: Damn, simple algo but WA#9! Help, please. TEST 9 1000 23 -256 31 -996 116 -255 34 -994 129 -255 38 -993 141 -254 41 -991 153 -254 44 -989 166 -253 47 -987 178 -253 50 -985 190 -252 53 -982 203 -252 56 -980 215 -251 59 -977 227 -250 62 -974 239 -250 65 -971 251 -249 68 -968 263 -248 71 -965 276 -247 74 -961 288 -246 77 -957 299 -245 80 -954 311 -244 83 -950 323 -243 86 -946 335 -242 89 -941 347 -241 92 -937 359 -240 95 -933 370 -239 98 -928 382 -238 101 -923 393 -237 104 -918 405 -235 107 -913 416 -234 110 -908 428 -233 113 -902 439 -231 115 -897 450 -230 118 -891 461 -228 121 -885 472 -227 124 -879 483 -225 127 -873 494 -224 129 -867 505 -222 132 -861 516 -221 135 -854 527 -219 137 -848 537 -217 140 -841 548 -216 143 -834 558 -214 145 -827 569 -212 148 -820 579 -210 150 -813 589 -208 153 -805 599 -207 156 -798 609 -205 158 -790 619 -203 160 -782 629 -201 163 -774 638 -199 165 -766 648 -197 168 -758 657 -195 170 -750 667 -193 172 -742 676 -191 175 -733 685 -188 177 -724 694 -186 179 -716 703 -184 182 -707 712 -182 184 -698 721 -179 186 -689 730 -177 188 -680 738 -175 190 -671 746 -173 192 -661 755 -170 194 -652 763 -168 196 -642 771 -165 198 -632 779 -163 200 -623 787 -160 202 -613 794 -158 204 -603 802 -155 206 -593 809 -153 208 -583 817 -150 210 -572 824 -148 212 -562 831 -145 213 -552 838 -143 215 -541 845 -140 217 -531 851 -137 218 -520 858 -135 220 -509 864 -132 222 -498 870 -129 223 -487 876 -126 225 -476 882 -124 226 -465 888 -121 228 -454 894 -118 229 -443 899 -115 230 -432 905 -112 232 -420 910 -109 233 -409 915 -107 234 -397 920 -104 236 -386 925 -101 237 -374 930 -98 238 -363 934 -95 239 -351 939 -92 240 -339 943 -89 241 -327 947 -86 242 -316 951 -83 243 -304 955 -80 244 -292 958 -77 245 -280 962 -74 246 -268 965 -71 247 -256 968 -68 247 -243 972 -65 248 -231 974 -62 249 -219 977 -59 250 -207 980 -56 250 -195 982 -53 251 -182 984 -49 251 -170 987 -46 252 -158 989 -43 252 -145 990 -40 253 -133 992 -37 253 -120 994 -34 254 -108 995 -31 254 -96 996 -28 254 -83 997 -25 254 -71 998 -21 255 -58 999 -18 255 -46 999 -15 255 -33 1000 -12 255 -21 1000 -9 255 -8 1000 -6 255 4 1000 -3 255 17 1000 1 255 29 999 4 255 42 999 7 255 54 998 10 254 67 997 13 254 79 996 16 254 92 995 19 254 104 994 22 253 117 992 26 253 129 991 29 252 141 989 32 252 154 987 35 251 166 985 38 251 178 983 41 250 191 980 44 250 203 978 47 249 215 975 50 248 227 972 53 248 239 969 56 247 251 966 59 246 264 963 62 245 276 959 65 244 287 955 68 243 299 952 71 242 311 948 74 241 323 944 77 240 335 939 80 239 347 935 83 238 358 931 86 237 370 926 89 236 381 921 92 235 393 916 95 233 404 911 98 232 416 906 101 231 427 900 103 229 438 895 106 228 449 889 109 226 460 883 112 225 471 877 115 223 482 871 117 222 493 865 120 220 504 859 123 219 515 852 125 217 525 846 128 215 536 839 131 214 546 832 133 212 557 825 136 210 567 818 138 208 577 811 141 206 587 803 144 205 597 796 146 203 607 788 148 201 617 780 151 199 626 772 153 197 636 764 156 195 645 756 158 193 655 748 160 191 664 740 163 189 673 731 165 186 682 722 167 184 691 714 170 182 700 705 172 180 709 696 174 177 718 687 176 175 726 678 178 173 734 669 180 171 743 659 182 168 751 650 184 166 759 640 186 163 767 630 188 161 775 621 190 158 782 611 192 156 790 601 194 153 797 591 196 151 805 581 198 148 812 570 200 146 819 560 201 143 826 550 203 141 833 539 205 138 839 529 206 135 846 518 208 133 852 507 210 130 858 496 211 127 864 485 213 124 870 474 214 122 876 463 216 119 882 452 217 116 887 441 218 113 893 430 220 110 898 418 221 107 903 407 222 105 908 395 224 102 913 384 225 99 918 372 226 96 922 361 227 93 927 349 228 90 931 337 229 87 935 325 230 84 939 314 231 81 943 302 232 78 946 290 233 75 950 278 234 72 953 266 235 69 956 254 235 66 960 241 236 63 962 229 237 60 965 217 238 57 968 205 238 54 970 193 239 51 972 180 239 47 975 168 240 44 977 156 240 41 978 143 241 38 980 131 241 35 982 118 242 32 983 106 242 29 984 94 242 26 985 81 242 23 986 69 243 19 987 56 243 16 987 44 243 13 988 31 243 10 988 19 243 7 988 6 243 4 988 -6 243 1 988 -19 243 -3 987 -31 243 -6 987 -44 243 -9 986 -56 242 -12 985 -69 242 -15 984 -81 242 -18 983 -94 242 -21 982 -106 241 -24 980 -119 241 -28 979 -131 240 -31 977 -143 240 -34 975 -156 239 -37 973 -168 239 -40 971 -180 238 -43 968 -193 238 -46 966 -205 237 -49 963 -217 236 -52 960 -229 236 -55 957 -241 235 -58 954 -253 234 -61 951 -266 233 -64 947 -278 232 -67 943 -289 231 -70 940 -301 230 -73 936 -313 229 -76 932 -325 228 -79 927 -337 227 -82 923 -349 226 -85 919 -360 225 -88 914 -372 224 -91 909 -383 223 -94 904 -395 221 -97 899 -406 220 -100 894 -418 219 -103 888 -429 217 -105 883 -440 216 -108 877 -451 214 -111 871 -462 213 -114 865 -473 211 -117 859 -484 210 -119 853 -495 208 -122 847 -506 207 -125 840 -517 205 -127 834 -527 203 -130 827 -538 202 -133 820 -548 200 -135 813 -559 198 -138 806 -569 196 -140 799 -579 194 -143 791 -589 193 -146 784 -599 191 -148 776 -609 189 -150 768 -619 187 -153 760 -628 185 -155 752 -638 183 -158 744 -647 181 -160 736 -657 179 -162 728 -666 177 -165 719 -675 174 -167 710 -684 172 -169 702 -693 170 -172 693 -702 168 -174 684 -711 165 -176 675 -720 163 -178 666 -728 161 -180 657 -736 159 -182 647 -745 156 -184 638 -753 154 -186 628 -761 151 -188 618 -769 149 -190 609 -777 146 -192 599 -784 144 -194 589 -792 141 -196 579 -799 139 -198 569 -807 136 -200 558 -814 134 -202 548 -821 131 -203 538 -828 129 -205 527 -835 126 -207 517 -841 123 -208 506 -848 121 -210 495 -854 118 -212 484 -860 115 -213 473 -866 112 -215 462 -872 110 -216 451 -878 107 -218 440 -884 104 -219 429 -889 101 -220 418 -895 98 -222 406 -900 95 -223 395 -905 93 -224 383 -910 90 -226 372 -915 87 -227 360 -920 84 -228 349 -924 81 -229 337 -929 78 -230 325 -933 75 -231 313 -937 72 -232 302 -941 69 -233 290 -945 66 -234 278 -948 63 -235 266 -952 60 -236 254 -955 57 -237 242 -958 54 -237 229 -962 51 -238 217 -964 48 -239 205 -967 45 -240 193 -970 42 -240 181 -972 39 -241 168 -974 35 -241 156 -977 32 -242 144 -979 29 -242 131 -980 26 -243 119 -982 23 -243 106 -984 20 -244 94 -985 17 -244 82 -986 14 -244 69 -987 11 -244 57 -988 7 -245 44 -989 4 -245 32 -989 1 -245 19 -990 -2 -245 7 -990 -5 -245 -6 -990 -8 -245 -18 -990 -11 -245 -31 -990 -15 -245 -43 -989 -18 -245 -56 -989 -21 -245 -68 -988 -24 -244 -81 -987 -27 -244 -93 -986 -30 -244 -106 -985 -33 -244 -118 -984 -36 -243 -131 -982 -40 -243 -143 -981 -43 -242 -155 -979 -46 -242 -168 -977 -49 -241 -180 -975 -52 -241 -192 -973 -55 -240 -205 -970 -58 -240 -217 -968 -61 -239 -229 -965 -64 -238 -241 -962 -67 -238 -253 -959 -70 -237 -265 -956 -73 -236 -278 -953 -76 -235 -290 -949 -79 -234 -301 -945 -82 -233 -313 -942 -85 -232 -325 -938 -88 -231 -337 -934 -91 -230 -349 -929 -94 -229 -361 -925 -97 -228 -372 -921 -100 -227 -384 -916 -103 -226 -395 -911 -106 -225 -407 -906 -109 -223 -418 -901 -112 -222 -430 -896 -115 -221 -441 -890 -117 -219 -452 -885 -120 -218 -463 -879 -123 -216 -474 -873 -126 -215 -485 -867 -129 -213 -496 -861 -131 -212 -507 -855 -134 -210 -518 -849 -137 -209 -529 -842 -139 -207 -539 -836 -142 -205 -550 -829 -145 -204 -560 -822 -147 -202 -571 -815 -150 -200 -581 -808 -152 -198 -591 -801 -155 -196 -601 -793 -158 -195 -611 -786 -160 -193 -621 -778 -162 -191 -631 -770 -165 -189 -640 -762 -167 -187 -650 -754 -170 -185 -659 -746 -172 -183 -669 -738 -174 -181 -678 -730 -177 -179 -687 -721 -179 -176 -696 -712 -181 -174 -705 -704 -184 -172 -714 -695 -186 -170 -723 -686 -188 -167 -732 -677 -190 -165 -740 -668 -192 -163 -748 -659 -194 -161 -757 -649 -196 -158 -765 -640 -198 -156 -773 -630 -200 -153 -781 -620 -202 -151 -789 -611 -204 -148 -796 -601 -206 -146 -804 -591 -208 -143 -811 -581 -210 -141 -819 -571 -212 -138 -826 -560 -214 -136 -833 -550 -215 -133 -840 -540 -217 -131 -847 -529 -219 -128 -853 -519 -220 -125 -860 -508 -222 -123 -866 -497 -224 -120 -872 -486 -225 -117 -878 -475 -227 -114 -884 -464 -228 -112 -890 -453 -230 -109 -896 -442 -231 -106 -901 -431 -232 -103 -907 -420 -234 -100 -912 -408 -235 -97 -917 -397 -236 -95 -922 -385 -238 -92 -927 -374 -239 -89 -932 -362 -240 -86 -936 -351 -241 -83 -941 -339 -242 -80 -945 -327 -243 -77 -949 -315 -244 -74 -953 -304 -245 -71 -957 -292 -246 -68 -960 -280 -247 -65 -964 -268 -248 -62 -967 -256 -249 -59 -970 -244 -249 -56 -974 -231 -250 -53 -976 -219 -251 -50 -979 -207 -252 -47 -982 -195 -252 -44 -984 -183 -253 -41 -986 -170 -253 -37 -989 -158 -254 -34 -991 -146 -254 -31 -992 -133 -255 -28 -994 -121 -255 -25 -996 -108 -256 -22 -997 -96 -256 -19 -998 -84 -256 -16 -999 -71 -256 -13 -1000 -59 -257 -9 -1001 -46 -257 -6 -1001 -34 -257 -3 -1002 -21 -257 0 -1002 -9 -257 3 -1002 4 -257 6 -1002 16 -257 9 -1002 29 -257 13 -1001 41 -257 16 -1001 54 -257 19 -1000 66 -256 22 -999 79 -256 25 -998 91 -256 28 -997 104 ANS 6398 Re: Damn, simple algo but WA#9! Help, please. That clears up a lot! :))))) |
|
|