Discussion of Problem 1185. Wall| Show all threads Hide all threads Show all messages Hide all messages | | WA 14 | Sirko | 1185. Wall | 14 Mar 2017 03:32 | 3 | WA 14 Sirko 5 Jan 2016 23:42 Can anybody give me some hint about test 14? Got AC using Graham's scan. Still can't figure out where's a bug in my previous O(N) solution. 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 | | similar to problem 1020 plus hint for #12 | kasarino | 1185. Wall | 16 Jan 2017 12:11 | 2 | 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 | | Something is grammaticaly incorrect in the problem description... | Georginsky | 1185. Wall | 4 Dec 2016 05:14 | 2 | "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/ | | Does "that it is accurate to 8 inches" requirement mean anything? | ToadMonster | 1185. Wall | 29 Feb 2016 18:25 | 1 | 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? | | clockwise order) | -XraY- | 1185. Wall | 6 Jan 2016 13:03 | 2 | 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... Hi. Can you remember, what was the problem with test 14? | | What does "Accurate to 8 inch" mean ? and Also why adding 2*pi*l to perimeter of polygon ? | competitivecoder | 1185. Wall | 20 Sep 2015 20:28 | 1 | 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. | | Simple=) | TakeOver | 1185. Wall | 20 Feb 2014 17:37 | 2 | | | Help Needed...WA12 thanks a lot! | DR. Zhihua Lai | 1185. Wall | 1 Apr 2013 19:44 | 1 | 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_algorithmbut 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 | | So easy | muhammad | 1185. Wall | 21 May 2012 14:40 | 2 | length of convex hull + 2 * PI * l :D Why did you said "length of convex hull + 2 * PI * l :D" | | Help me ! | hnivhnivt95 | 1185. Wall | 21 May 2012 14:22 | 1 | Can you have me why solution is 1628 ?? | | WA12. Give me hint, plz. | Programmer | 1185. Wall | 31 Aug 2010 18:20 | 4 | I don`t know what bug is in my programm. Who can give me this test. Re: Help me. Vedernikoff Sergey (HSE: EconomicsForever!) 11 Feb 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) 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. | | Why WA#1 | sim40 | 1185. Wall | 9 Aug 2009 23:49 | 1 | nevermind :)
Edited by author 09.08.2009 23:57 | | wa#10. how to output? | AlMag(VNTU) | 1185. Wall | 21 May 2009 18:36 | 3 | cout << (int)(res+0.5) << endl;
is it correct?
Edited by author 03.04.2009 20:39 yes it's correct
Edited by author 01.08.2009 23:14 | | Judges, who can help me? WA 12. | Programmer | 1185. Wall | 24 Jan 2009 00:07 | 1 | Plz, give me hint.
Edited by author 24.01.2009 00:20
Edited by author 24.01.2009 00:20 | | Damn, simple algo but WA#9! Help, please. | Alexey | 1185. Wall | 26 Oct 2008 04:24 | 5 | 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. 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. 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 That clears up a lot! :))))) | | problem with accuracy ? | Todor Tsonkov | 1185. Wall | 12 Aug 2006 21:08 | 1 | I use Graham Scan which is N*logN but I get WA, strange..
Edited by author 12.08.2006 21:09 | | Little question | AIT | 1185. Wall | 1 Apr 2006 20:55 | 5 | 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 It doesn't used for accuracy in calculations ( i ask why <=0 doesn't
work ) if vp<eps then
here it means vp<=0 when eps=0.00000000001
and vp<0 when eps=0 | | Does anyone know why this problem was rejudged?(+) | Valentin Mihov | 1185. Wall | 10 Apr 2004 02:21 | 1 | 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... | | Crash! | lzoi_HsWy | 1185. Wall | 12 Aug 2003 09:06 | 2 | Crash! lzoi_HsWy 29 Dec 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. 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. | | why i got WA | coma | 1185. Wall | 10 Jun 2003 12:18 | 3 | 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;
} > 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;
> } > > 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;
> > } |
|
|
