ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1185. Wall

Damn, 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.
Posted by IYI_Blade 26 Aug 2006 22:24
I get WA #9, too :(
Re: Damn, simple algo but WA#9! Help, please.
Posted by Tbilisi SU: Eldar Bogdanov 13 Sep 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.
Re: Damn, simple algo but WA#9! Help, please.
Posted by beststu 1 Jun 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
Re: Damn, simple algo but WA#9! Help, please.
Posted by кукурузо (Ulyanovsk) 26 Oct 2008 04:24
That clears up a lot! :)))))