| ENG RUS | Timus Online Judge |
Обсуждение задачи 1185. Wallkasarino similar to problem 1020 plus hint for #12 [2] // Задача 1185. Wall 29 фев 2016 16:17 1) in Graham scan, sort points by polar angle, for equal polar angles - by distance from p0 2) second part of the problem is similar to problem 1020 c_pp Re: similar to problem 1020 plus hint for #12 // Задача 1185. Wall 16 янв 2017 12:11 Alex_Gu Re: similar to problem 1020 plus hint for #12 // Задача 1185. Wall 25 апр 2024 11:47 my perception is, that to reproduce W12 you are to make a wall from 4 vertices, placed in line Sirko WA 14 [2] // Задача 1185. Wall 5 янв 2016 23:42 Can anybody give me some hint about test 14? Sirko Re: WA 14 [1] // Задача 1185. Wall 11 янв 2016 03:02 Got AC using Graham's scan. Still can't figure out where's a bug in my previous O(N) solution. Mykhaylo Re: WA 14 // Задача 1185. Wall 14 мар 2017 03:32 If you go throw points clockwise and remove one that creates not clockwise angle. This idea is wrong. Counter test: 8 1 0 0 1 3 3 3 1 1 4 0 2 1 5 3 5 -1 Result is 23 Edited by author 14.03.2017 03:32 Edited by author 14.03.2017 03:32 Georginsky Something is grammaticaly incorrect in the problem description... [1] // Задача 1185. Wall 4 дек 2016 04:15 "If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will LOOSE his head." http://grammarist.com/usage/loose-lose/ Jane Soboleva (SumNU) Re: Something is grammaticaly incorrect in the problem description... // Задача 1185. Wall 4 дек 2016 05:14 Shakespeare, i dare to say!~ https://books.google.com.ua/books?id=Ds0yAQAAMAAJ&pg=PA282&lpg=PA282&dq=loose+his+head#v=onepage&q=loose%20his%20head&f=false https://books.google.com.ua/books?id=1joRAwAAQBAJ&pg=PA189&lpg=PA189&dq=shakespeare+%22loose%22+his+head#v=onepage&q=shakespeare%20%22loose%22%20his%20head&f=false ToadMonster Does "that it is accurate to 8 inches" requirement mean anything? // Задача 1185. Wall 29 фев 2016 18:25 There is task fragment: "However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches)" I thought it means that result should be int and (result*12) should be divided by 8 without reminder. I received WA3. When I ignored requirement and used simple rounding like int(result+0.5) I got ac. So, does requirement mean anything? Maybe it should be removed from task? -XraY- clockwise order) [1] // Задача 1185. Wall 31 май 2011 17:20 What does it mean: "clockwise order"? How do you define clockwise order in notconvex polygon? For example: in picture like a snail what roundabout way is turned in the clockwise direction and what is not? Sorry for bad Enlish... Sirko Re: clockwise order) // Задача 1185. Wall 6 янв 2016 13:03 Hi. Can you remember, what was the problem with test 14? competitivecoder What does "Accurate to 8 inch" mean ? and Also why adding 2*pi*l to perimeter of polygon ? // Задача 1185. Wall 20 сен 2015 20:28 Please help 1) What does accurate to 8 inch mean.Does it mean accurate upto (8/12) ? 2) Why do we add 2*pi*l to the perimeter of polygon ?Anybody please help. TakeOver Simple=) [1] // Задача 1185. Wall 23 дек 2012 15:09 ASK Re: Simple=) // Задача 1185. Wall 20 фев 2014 17:37 Nope, <https://en.wikipedia.org/wiki/Graham_scan> is simpler and faster. DR. Zhihua Lai Help Needed...WA12 thanks a lot! // Задача 1185. Wall 1 апр 2013 19:44 What is wrong with this code program Project4; {$APPTYPE CONSOLE} {$M 16777216} uses Math; type Pt = record x, y: integer; end; float = Extended; function left(const p1, p2, p3: Pt): boolean; inline; begin Result := ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x)) > 0; end; function dist(const p1, p2: Pt): float; inline; begin Result := Sqrt(Sqr(p1.x - p2.x) + Sqr(p1.y - p2.y)); end; var ans: float; i, n, l, j: integer; p, s: array[1..1001] of Pt; pointOnHull, endPoint: Pt; begin Readln(n, l); pointOnHull.x := 1000001; pointOnHull.y := 1000001; for i := 1 to n do begin Readln(p[i].x, p[i].y); if (p[i].x < pointOnHull.x) then begin pointOnHull := p[i]; end else if ((p[i].x = pointOnHull.x) and (p[i].y < pointOnHull.y)) then begin pointOnHull := p[i]; end; end; j := 1; repeat s[j] := pointOnHull; endPoint := p[1]; for i := 2 to n do begin if (((endpoint.x = pointOnHull.x) and (endpoint.y = pointOnHull.y)) or (left(p[i], pointOnHull, endpoint))) then begin endpoint := p[i]; end; end; Inc(j); pointOnHull := endPoint; until (endPoint.x = s[1].x) and (endPoint.y = s[1].y); ans := dist(s[1], s[j - 1]); for i := 2 to j - 1 do begin ans := ans + dist(s[i], s[i - 1]); end; ans := Round(ans + 2 * PI * l); Writeln(ans:0:0); {$IFNDEF ONLINE_JUDGE} Readln; {$ENDIF} end. This uses 'gift-wrapping' algorithm described in http://en.wikipedia.org/wiki/Gift_wrapping_algorithm but it can't pass test 12. As you can see, I use 'extended', so it is not problem of precision. Edited by author 01.04.2013 19:45 Edited by author 01.04.2013 19:47 muhammad So easy [1] // Задача 1185. Wall 31 авг 2010 11:53 length of convex hull + 2 * PI * l :D hnivhnivt95 Re: So easy // Задача 1185. Wall 21 май 2012 14:40 Why did you said "length of convex hull + 2 * PI * l :D" hnivhnivt95 Help me ! // Задача 1185. Wall 21 май 2012 14:22 Can you have me why solution is 1628 ?? Programmer WA12. Give me hint, plz. [3] // Задача 1185. Wall 24 янв 2009 00:14 Programmer Help me. [1] // Задача 1185. Wall 11 фев 2009 02:17 I don`t know what bug is in my programm. Who can give me this test. Vedernikoff Sergey (HSE: EconomicsForever!) Re: Help me. // Задача 1185. Wall 11 фев 2009 02:31 As I remember, in 12th test the point is in precision. If you write in Pascal, use Extended (in C++ - double), use very accurate value for PI (3.1415926 is NOT enough), in Pascal use standard constant "pi", in C - 2.0*acos(0.0) Artem Khizha [DNU] Re: WA12. Give me hint, plz. // Задача 1185. Wall 31 авг 2010 18:20 Well, in my case the reason for WA#12 was inproper implementation of Graham's algorithm, not a precision. Be careful with cases, when there are points with the same polar angle. sim40 Why WA#1 // Задача 1185. Wall 9 авг 2009 23:49 nevermind :) Edited by author 09.08.2009 23:57 AlMag(VNTU) wa#10. how to output? [2] // Задача 1185. Wall 3 апр 2009 20:25 cout << (int)(res+0.5) << endl; is it correct? AlMag(VNTU) Re: wa#10. how to output? // Задача 1185. Wall 3 апр 2009 20:38 Edited by author 03.04.2009 20:39 beegii Re: wa#10. how to output? // Задача 1185. Wall 21 май 2009 18:36 yes it's correct Edited by author 01.08.2009 23:14 Programmer Judges, who can help me? WA 12. // Задача 1185. Wall 24 янв 2009 00:07 Plz, give me hint. Edited by author 24.01.2009 00:20 Edited by author 24.01.2009 00:20 Alexey Damn, simple algo but WA#9! Help, please. [4] // Задача 1185. Wall 9 авг 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. IYI_Blade Re: Damn, simple algo but WA#9! Help, please. [3] // Задача 1185. Wall 26 авг 2006 22:24 I get WA #9, too :( Tbilisi SU: Eldar Bogdanov Re: Damn, simple algo but WA#9! Help, please. [2] // Задача 1185. Wall 13 сен 2006 20:49 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. beststu Re: Damn, simple algo but WA#9! Help, please. [1] // Задача 1185. Wall 1 июн 2008 09:26 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 кукурузо (Ulyanovsk) Re: Damn, simple algo but WA#9! Help, please. // Задача 1185. Wall 26 окт 2008 04:24 That clears up a lot! :))))) Todor Tsonkov problem with accuracy ? // Задача 1185. Wall 12 авг 2006 21:08 I use Graham Scan which is N*logN but I get WA, strange.. Edited by author 12.08.2006 21:09 AIT Little question [4] // Задача 1185. Wall 14 мар 2003 22:28 const eps = 0; type real = extended; type tpoint = record x, y: real; end; var n, l: longint; mas: array [1..1000] of tpoint; an: array [1..1000] of real; ob: array [1..1000] of boolean; ans: array [1..1000] of longint; a, ang: real; i, j, k: longint; c, t: tpoint; v: array [1..3] of longint; function getan(p: tpoint): real; var x: real; begin if p.x=0 then begin if p.y>0 then getan:=pi/2 else getan:=-pi/2; exit; end; x:=p.y/p.x; getan:=arctan(x); end; procedure fconvex; var vp: real; v1, v2: tpoint; begin v[1]:=2; v[2]:=3; v[3]:=4; i:=4; repeat v1.x:=mas[v[2]].x-mas[v[1]].x; v1.y:=mas[v[2]].y-mas[v [1]].y; v2.x:=mas[v[3]].x-mas[v[2]].x; v2.y:=mas[v[3]].y-mas[v [2]].y; vp:=v1.x*v2.y-v1.y*v2.x; if vp<eps then begin ob[v[2]]:=false; dec(k); v[2]:=v[1]; dec(v[1]); while ob[v[1]]= false do dec(v[1]); end else begin v[1]:=v[2]; v[2]:=v[3]; i:=i mod n + 1; v[3]:=i; end; until i=2; end; begin read(n, l); c.x:=maxlongint; c.y:=maxlongint; fillchar(ob, sizeof(ob), false); for i:=1 to n do begin read(mas[i].x, mas[i].y); if (mas[i].x<c.x)or((mas[i].y<c.y)and(mas[i].x=c.x)) then c:=mas[i]; end; for i:=1 to n do begin t.x:=mas[i].x-c.x;t.y:=mas[i].y-c.y; an[i]:=getan(t); j:=i; while (j>1)and(an[j]<an[j-1]) do begin a:=an[j]; an[j]:=an[j-1]; an[j-1]:=a; t:=mas[j]; mas[j]:=mas[j-1]; mas[j-1]:=t; dec(j); end; end; fillchar(ob, sizeof(ob), true); k:=n; if n>3 then fconvex; i:=1; j:=0; repeat while (i<n)and(not ob[i]) do inc(i); inc(j); ans[j]:=i; inc(i); until j=k; a:=0; for i:=1 to k-1 do begin ang:=sqr(mas[ans[i]].x-mas[ans[i+1]].x)+sqr(mas[ans[i]].y- mas[ans[i+1]].y); ang:=sqrt(ang); a:=a+ang; end; ang:=sqrt(sqr(mas[ans[k]].x-mas[ans[1]].x)+sqr(mas[ans[k]].y-mas [ans[1]].y)); a:=a+ang; a:=a+2*pi*l; writeln(a:0:0); end. Why my solution works if eps=0 and doesn't work if eps is for example 0.00000000001 Locomotive i think because test dataes has calculated by eps=0 . [2] // Задача 1185. Wall 14 мар 2003 22:32 Miguel Angel Epsilon is not needed for this problem (-) [1] // Задача 1185. Wall 15 мар 2003 07:47 > AIT Thanks, but... // Задача 1185. Wall 16 мар 2003 23:48 It doesn't used for accuracy in calculations ( i ask why <=0 doesn't work ) currently unnamed... Re: Little question // Задача 1185. Wall 1 апр 2006 20:55 if vp<eps then here it means vp<=0 when eps=0.00000000001 and vp<0 when eps=0 Valentin Mihov Does anyone know why this problem was rejudged?(+) // Задача 1185. Wall 10 апр 2004 02:21 My solution which was ACed is now wrong. Actually I accepted it after lot of submits and after lot of corrected bugs. The interesting this is that the solution of this problem is not something complex... lzoi_HsWy Crash! [1] // Задача 1185. Wall 29 дек 2002 10:59 program p1185; const maxx=1000; type rec=record x,y:integer; end; arr=array [1..maxx] of rec; var tdot,dot:arr; n,l:integer; s:extended; {$APPTYPE CONSOLE} procedure init; var i:integer; begin readln(n,l); for i:=1 to n do readln(tdot[i].y,tdot[i].x); end; procedure solve; var i:integer; function multi(a,b,c:rec):integer; begin multi:=(a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y); end; procedure find(n:integer); var i:integer; t:rec; begin for i:=1 to n do if (tdot[i].y<tdot[1].y) or ((tdot[i].y=tdot[1].y) and (tdot [i].x<tdot[i].x)) then begin t:=tdot[i]; tdot[i]:=tdot[1]; tdot[1]:=t; end; end; procedure scan(k:integer); var stack:array [1..maxx] of integer; i,top:integer; begin for i:=1 to 3 do stack[i]:=i; top:=3; for i:=4 to k do begin while (multi(tdot[i],tdot[stack[top]],tdot[stack[top-1]]) >0) do dec(top); inc(top); stack[top]:=i; end; for i:=1 to top do dot[i]:=tdot[stack[i]]; n:=top; end; function gg(a,b:rec):extended; begin gg:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); end; begin find(n); scan(n); for i:=1 to (n-1) do begin s:=s+gg(dot[i],dot[i+1]); end; s:=s+gg(dot[n],dot[1]); s:=s+l*2*pi; end; procedure sout; begin writeln(s:0:0); end; begin init; solve; sout; end. 永遠の痛 Crash, too!! help!!! // Задача 1185. Wall 12 авг 2003 09:06 it is as same as ZJU1465 :( I got RuntimeError201 there... {$N+} const maxn=1001; type postype=record x,y:double; end; var ti,tn,n,top:longint; list:array[0..maxn] of postype; stk:array[1..maxn] of longint; feet:double; procedure swap(var a,b:postype); var t:postype; begin t:=a; a:=b; b:=t; end; function multi(var p1,p2,p0:postype):double; begin multi:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); end; function comp(var p1,p2:postype):boolean; var t:double; begin t:=multi(p1,p2,list[0]); if (t>0) or (t=0) and (sqr(p1.x-list[0].x)+sqr(p1.y-list[0].y)< sqr(p2.x-list[0].x)+sqr(p2.y-list[0].y)) then comp:=true else comp:=false; end; procedure sort(p,r:longint); var i,j:longint; x:postype; begin if r-p+1<=5 then begin for j:=p+1 to r do begin i:=j; while (i>1) and (comp(list[i],list[i-1])) do begin swap(list[i],list[i-1]); dec(i); end; end; end else begin x:=list[p+random(r-p+1)]; i:=p; j:=r; repeat while comp(list[i],x) do inc(i); while comp(x,list[j]) do dec(j); if i<j then swap(list[i],list[j]); until i>=j; sort(p,j); sort(j+1,r); end; end; procedure init; var i:longint; begin readln(n,feet); if n=0 then halt; for i:=0 to n-1 do begin readln(list[i].x,list[i].y); if (list[i].y<list[0].y) or ((list[i].y=list[0].y) and (list[i].x<list[0].x)) then swap(list[0],list[i]); end; sort(1,n-1); end; procedure graham; var i:longint; d:double; begin for i:=1 to 3 do stk[i]:=i-1; top:=3; for i:=3 to n-1 do begin while multi(list[i],list[stk[top]],list[stk[top-1]])>=0 do dec(top); inc(top); stk[top]:=i; end; d:=0; for i:=1 to top-1 do d:=d+ sqrt ( (list[stk[i]].x-list[stk[i+1]].x)*(list[stk [i]].x-list[stk[i+1]].x) + (list[stk[i]].y-list[stk[i+1]].y)*(list[stk[i]].y-list[stk [i+1]].y)); d:=d+ sqrt ( (list[stk[top]].x-list[stk[1]].x)*(list[stk [top]].x-list[stk[1]].x) + (list[stk[top]].y-list[stk[1]].y)*(list[stk [top]].y-list[stk[1]].y)); writeln(round(d+feet*3.141592653*2)); end; begin assign(input,'1465.in'); reset(input); readln(tn); for ti:=1 to tn do begin init; graham; if ti<>tn then writeln; end; end. coma why i got WA [2] // Задача 1185. Wall 10 июн 2003 12:07 first i find the convex polygon the answer is equal to the length of the convex polygon and 2*pi*l is it right? #include <stdio.h> #include <math.h> #define PI 3.1415926535 struct point { double x,y; }; struct point p[1001]; int n; double l; double dis; double mul(point p1,point p2,point p0) { return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.y)*(p1.y-p0.y)); } double dist(point q,point p) { return (sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y))); } void init() { int i,j; //FILE *fp=fopen("input.in","r"); scanf("%d%lf",&n,&l); for (i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); } void work() { int i,j; int s; int next[1001]; for (i=0;i<n;i++) next[i]=(i+1)%n; s=1; while (s==1) { s=0; for (i=0;i<n;i++) if (next[i]!=-1) { if (mul(p[next[i]],p[next[next[i]]],p[i])>=-1e-14) { s=1; j=next[i]; next[i]=next[next[i]]; next[j]=-1; } } } dis=0; for (i=0;i<n;i++) if (next[i]!=-1) dis=dis+dist(p[i],p[next[i]]); dis=dis+2*PI*l; printf("%.0lf\n",dis+0.5); } main() { init(); work(); return 0; } coma the problem is 1185 [1] // Задача 1185. Wall 10 июн 2003 12:15 > first i find the convex polygon > the answer is equal to the length of the convex polygon and 2*pi*l > > is it right? > > > #include <stdio.h> > #include <math.h> > > #define PI 3.1415926535 > > struct point > { > double x,y; > }; > > struct point p[1001]; > int n; > double l; > double dis; > > double mul(point p1,point p2,point p0) > { > return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.y)*(p1.y-p0.y)); > } > > double dist(point q,point p) > { > return (sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y))); > } > > void init() > { > int i,j; > //FILE *fp=fopen("input.in","r"); > scanf("%d%lf",&n,&l); > for (i=0;i<n;i++) > scanf("%lf%lf",&p[i].x,&p[i].y); > } > > > void work() > { > int i,j; > int s; > int next[1001]; > for (i=0;i<n;i++) > next[i]=(i+1)%n; > s=1; > while (s==1) > { > s=0; > for (i=0;i<n;i++) > if (next[i]!=-1) > { > if (mul(p[next[i]],p[next[next[i]]],p[i])>=-1e-14) > { > s=1; > j=next[i]; > next[i]=next[next[i]]; > next[j]=-1; > } > } > } > dis=0; > for (i=0;i<n;i++) > if (next[i]!=-1) > dis=dis+dist(p[i],p[next[i]]); > dis=dis+2*PI*l; > printf("%.0lf\n",dis+0.5); > } > > main() > { > init(); > work(); > return 0; > } coma who can help me???i've got WA for mant times // Задача 1185. Wall 10 июн 2003 12:18 > > first i find the convex polygon > > the answer is equal to the length of the convex polygon and 2*pi*l > > > > is it right? > > > > > > #include <stdio.h> > > #include <math.h> > > > > #define PI 3.1415926535 > > > > struct point > > { > > double x,y; > > }; > > > > struct point p[1001]; > > int n; > > double l; > > double dis; > > > > double mul(point p1,point p2,point p0) > > { > > return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.y)*(p1.y-p0.y)); > > } > > > > double dist(point q,point p) > > { > > return (sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y))); > > } > > > > void init() > > { > > int i,j; > > //FILE *fp=fopen("input.in","r"); > > scanf("%d%lf",&n,&l); > > for (i=0;i<n;i++) > > scanf("%lf%lf",&p[i].x,&p[i].y); > > } > > > > > > void work() > > { > > int i,j; > > int s; > > int next[1001]; > > for (i=0;i<n;i++) > > next[i]=(i+1)%n; > > s=1; > > while (s==1) > > { > > s=0; > > for (i=0;i<n;i++) > > if (next[i]!=-1) > > { > > if (mul(p[next[i]],p[next[next[i]]],p[i])>=-1e-14) > > { > > s=1; > > j=next[i]; > > next[i]=next[next[i]]; > > next[j]=-1; > > } > > } > > } > > dis=0; > > for (i=0;i<n;i++) > > if (next[i]!=-1) > > dis=dis+dist(p[i],p[next[i]]); > > dis=dis+2*PI*l; > > printf("%.0lf\n",dis+0.5); > > } > > > > main() > > { > > init(); > > work(); > > return 0; > > }
|