11382 - Fear of The Dark

Moderator: Board moderators

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...

11382 - Fear of The Dark

I have been trying for a while now to find the best way to do this problem. .

The way I am thinking about doing this problem is as follows:

Read a ghost's posistion, check and see if this ghost is independent from all other ghosts. I define independent as that its angle between its two points from the shooter does not contain any endpoints of other ghosts and vice-versa no other ghost contains the endpoints of this ghost.

If it is independent you add it to the list and continue reading ghosts. If it is not independent then you check and see if this ghost is contained fully by one ghost. If so continue reading as this ghost is essentially useless information. Otherwise, check the other extreme and see if this ghost fully contains one or multiple ghosts and remove them for the same reason. If any ghosts were removed recheck if it is independent.

If it is still not independent then the last case is the tricky one. Since we have determined this ghost is not independent it means one point of this ghost is contained by another ghost or both points are contained by two different ghosts.

There are two ways I can think of to deal with this case. The hard way would be to determine the point of intersection on the ghost where the shot would be and then make the contained point to that new value. However this means that the new point will most likely not be an integer point and complicate further computations.

My other thought would be to just set the contained point to the containing ghosts endpoint so that it no longer contains that point and now you have the added usefulness that the new point is an integer point and that its new angle will be the exact same as if you were to calculate the intersection and change to that point. The only other thing you would need to worry about is when this ghost has both its endpoints contained by two different ghosts if the end result is that the new endpoints are the same value then really this ghost was completely covered by those two ghosts and you can disregard this ghost and continue reading.

Now that you have all that tricky stuff dealt with you can go ahead and try and calculate the minimum angle to kill all remaining ghosts with the specified amount of shots. This is also a little tricky and I havent come up with a definte solution.

For example taking the sample input with an added point to better explain the last case:

Code: Select all

``````1
5 3 0 0
2 2 2 -2 (ghost 1)
3 3 3 1 (ghost 2)
4 2 8 2 (ghost 3)
-6 1 -6 0 (ghost 4)
4 -1 1 -4 (ghost 5)
``````
As shown in a graph:

After going through the steps I have explained ghost 2 and 3 can be removed since they are fully contained by ghost 1. Also since ghost 5 has one point contained by ghost 1 we move ghost's 5 endpoint to ghost 1's endpoint as shown:

(note: ghost 1's endpoint could also have been changed to ghost 5's endpoint and given the same effect.)

Now you have 3 remaining ghosts and you can calculate the solution, which for this I got to be 60.4818.

So after hearing all of my thoughts, you guys spot any problems with my thinking or have any thing else to add to help solve this difficult problem?
Last edited by CMG on Mon Jan 07, 2008 9:15 am, edited 5 times in total.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Well... convert the lines into angle, it will make the problem very easy
Self judging is the best judging!

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
Yes, thats implied in the problem and my thoughts above. My major problem is how to exactly figure out the minimum angle needed to kill all ghosts for any test case after the intial setup is complete like in my last graph. It can turn out to be a lot more complicated than the one in the test case.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
do a binary search
Self judging is the best judging!

CMG
New poster
Posts: 37
Joined: Sat Dec 08, 2007 5:01 am
Location: ...
Care to elaborate any? Binary search of what?

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
CMG wrote:Care to elaborate any? Binary search of what?
For angle, of course.

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm
Anyone who got ac can give some tricky test cases?
I used bsearch and greedy,but got wa.

Code: Select all

``````10

42 8 -3666 -3500
9169 5724 1478 -642
-3038 -5536 -4295 -1855
-6719 6827 -39 -9509
-7005 1942 -5173 -4564
2391 4604 -6098 -9847
-9708 2382 7421 8716
9718 9895 -4553 -8274
4771 1538 -8131 9912
-4333 -3701 7035 -106
-1297 -6189 1322 333
7673 -5336 5141 -2289
-1747 -3132 -4453 -2356
2662 2757 -9963 2859
-1277 -259 -2471 -9222
2316 -6965 -7810 -8158
-9712 106 -960 -1058
9264 -7352 -2554 -6195
5890 -3271 -5630 5350
5006 1101 -5607 -6452
9629 2623 -5916 9954
8756 1840 -5034 -2624
3931 -3692 6944 2439
-5374 1323 -4463 -8462
6118 -7918 -7071 6541
-5167 1115 -5361 -342
-7296 -70 3977 -7694
1673 -7614 -4979 -1255
-3076 9072 -3730 -4171
-3223 5573 -4903 6512
-6014 3290 -839 8636
-7645 -5233 -6345 5574
-5969 2052 -2650 -8850
6941 -8276 3966 -6570
1107 191 8007 1337
5457 2287 -2247 383
4945 -1091 2209 -242
-5779 8588 -3578 -5054
-2494 3030 6413 -832
-9100 2591 8762 -8345
7410 -3641 -2376 -9463
-8452 -3517 -2405 -5959
-6398 -5650 291 836

25 1 -5404 -5979
-2652 -6801 9668 -5516
-1719 -5266 -9947 -8001
-3582 -2062 -3100 -6212
8127 -9533 -6272 4893
-5352 -7517 7807 -7579
4310 -3383 -7187 -486
4309 -2384 8935 7451
-9400 -4751 6519 1556
-7202 303 -3776 1008
-4156 2609 4989 2702
-6805 -9515 -6907 4343
523 -8413 -686 -497
-2552 -4800 3458 -3382
-9420 9796 4798 5281
9589 -9202 -1991 -2843
-9528 -6378 8538 2292
-3962 -5821 8190 -343
-2042 -3809 9815 -7112
9156 1511 6202 -7366
-5728 -9945 -9672 -7354
-3638 -5114 8875 -1567
-131 -9858 -6156 -8584
-8119 1998 322 8651
21 -4301 -6443 -1524
-2108 -5611 -4925 712

1 1 -8997 -3131
7861 4688 3401 -211

6 4 -4998 585
-5818 285 -2912 1426
-1383 -6243 -168 932
-5831 -7846 -4279 7189
9976 1329 -7632 -1308
-8575 555 -6566 6549
-2559 -488 145 8060

19 4 6139 2423
6279 -4004 6687 2529
-7451 7437 9866 2949
-9807 -6805 -6703 -9584
-1714 6105 -5512 6282
2455 -4266 8114 1701
1316 -9329 -4214 2263
-5687 -5645 1185 -9947
-9088 808 -8168 -9055
-5687 -2244 -1679 9558
-6354 -2018 -9519 -5856
-6804 -9778 -2871 -7839
-4465 -9550 1173 466
2044 -8341 -3708 -3561
7253 -9976 -3846 -490
-5255 -9351 3186 -1687
-5526 -1978 -7832 4018
8787 -95 7958 -2609
202 -6375 -3523 -5586
-686 -4176 -666 -4126

23 10 1833 -1930
-2513 -1703 -2482 -1823
7773 2270 -8237 -7332
7192 3985 -6898 -1520
-787 -2373 -5198 -5901
527 -7375 -8457 -8076
1023 -28 3061 4181
1003 -2568 7505 -2407
-7275 3031 -1508 -9858
7222 1286 3064 -2100
9187 -1640 -7587 974
4270 -830 -9765 833
9711 -4240 8896 -5333
-2715 2550 -9860 3694
-7305 -8376 -1981 -7875
-3424 -8306 -7342 -3698
7371 -7534 -5322 -7407
-6149 -4516 -8982 -1536
-8881 -6848 -7200 8087
1060 -8074 -990 -5243
2170 -9685 -424 227
2043 -7242 -2836 -4891
-2118 7086 -435 -6513
-423 4474 -7375 -4373

30 9 -4577 -1480
-3098 4962 -9877 -5404
-6263 3261 195 2525
-8736 -1740 -3798 -1884
-4970 -9674 -989 771
-3589 -4453 -8847 -8480
-210 4924 188 -8237
-5060 -9149 8662 3829
900 7713 8958 7578
-1635 3007 1477 -8800
-3942 -3561 -7697 2760
9357 -7676 -3523 -4892
-8887 4887 9801 -7150
4460 -7572 2993 -2616
9405 -3460 1111 -1296
2835 2356 -3928 -650
8823 4485 -9444 -6784
-8374 -643 -1474 3357
-663 -6729 -6131 -639
2896 3022 -383 112
2717 8696 1585 -5959
-5577 -5871 -5771 -5435
-3441 -1068 -7704 -145
2053 6962 -6416 -266
-3346 6972 -8543 4369
-7468 -7037 -7393 -7517
-9089 1635 67 -7152
-5325 2938 -7777 -7858
-6246 -3489 -7259 -9825
-8541 7825 -6779 7870
-8374 1934 5205 1783

1 9 -7721 -7299
2193 2734 -8363 -3466

7 4 176 -4295
-3038 548 5881 -9700
4413 6641 9855 -5145
3142 1462 -2389 877
-9576 2678 -8248 8443
-1704 2673 40 -687
-9125 -9928 2818 -9390
-8983 4932 -1888 695

20 2 -9960 -3512
-1315 9090 9497 -7411
-4010 5145 9353 9314
8651 -3260 -7956 1258
-9665 -1241 1192 -2395
-4736 2181 -1497 -6171
-6225 -9392 -708 -4003
7549 -444 -4439 1627
-3533 -459 -3871 1240
-2187 -826 -9399 -3923
-9785 -1317 -1787 -6008
-4176 -4399 -6608 5759
-7330 -3572 -1973 -5916
75 8786 5498 -5030
-3713 -6153 2604 -9497
-8779 -7337 -4294 -7637
-990 -7829 -2511 8240
2164 -4458 -2381 -9087
-2409 -3296 1818 -768
-9250 -4795 -5025 -8461
-9697 1422 -8902 1247
``````

Code: Select all

``````45.0000
-1.0000
11.6297
86.0978
90.0000
31.9114
40.0000
6.0185
73.3084
79.8952
``````
who can tell me whether the output above is correct?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
My AC code outputs:

Code: Select all

``````45.0000
-1.0000
11.6297
86.0978
90.0000
36.0000
40.0000
6.0185
73.3084
79.8952
``````
-----
Rio

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm
thanks very much!now I get ac immediately by debugging step by step.
Add one condition and mark the some unnecessary start points.
hope it can help anyone who got wa for this problem!
thanks again,rio!