10233 - Dermuba Triangle

[yaro]

Hi,

My code got WA, I don't know why. Are there any tricky cases?

Thanks for any help.

[yaro]

OK, I found a mistake (switched int to long long) and got AC.

[turcse143]

hi,
everybody ples give any idea of this problem.
i don't understand.
ples help me.

[stcheung]

Here's some hint. Note that I might have done it the hard way.

(1) Given the input, calculate the "coordinate" with respective to house 0. For instance, here are some coordinates.
0: (0, 0)
1: (-1, -1)
2: (0, -1)
3: (1, -1)
4: (-2, -2)
5: (-1, -2)
6: (0, -2)
7: (1, -2)
8: (2, -2)
9: (-3, -3)
10: (-2, -3)
11: (-1, -3)
...

(2) Calculate the horizontal distance between house 1 and house 2.

(3) Calculate the vertical distance between house 0 and house 1.

(4) Calculate the vertical distance between house 1 and house 2.

Combine these info to derive the final distance. We need (4) above because the vertical distance between house 0 and house 1 is different than that between house 0 and house 2. So you need to adjust it for these "upside-down" houses like 2, 5, 7, 10. All these distances in (2)-(4) can be derived by recognizing that 0.577 (distance between house 9 and house 10) is sqrt(3) / 3.

This problem is mostly mathematical in nature so once you figured out these distances you are 80-90% done.

[jenovaforum]

I'm trying to understand why switching over to long long int helps, and here is my hypothesis:

Floating points go up to 2^80

Integers go up to 2^31-1 but the problem states all triangles are within this range.

if you square an integer before converting it to a float, you'll spill over...

Does this sound right?

[fizzlesticks]

Does anyone have some sample input for this problem, my program has worked for everything I tried and I'm kind of convinced I'm getting WA because of some floating point error or something.

[brianfry713]

Random input:

Code: Select all

511588181 652657228
1852756952 1790865963
1140952686 136318373
2085991715 1726961145
1881899363 1978701405
561122256 1959090857
988078148 1510333718
1711549392 955633073
2006051356 1013306190
2140695990 1075491637
1261436914 1694118744
1157750383 718851424
1671851593 895934864
660080930 1309509877
1158971203 754089009
1406746237 2007502684
1650884999 1670559384
1806877757 1112019542
691497039 644354038
475571795 1745385824
1556993033 425912754
1936246473 1036694051
1992327124 397587533
1410893723 1500312217
428320206 1850894832
1397529928 1404106065
2122957489 1689757121
438208337 407796663
1717306541 1647325435
253930796 1098289268
958308304 728794096
251869832 1660677033
625212927 461709656
1106063694 2058747589
1656649765 1316709967
1742622721 1581635489
470845892 1066159150
1463746684 1531385546
884214116 315689369
19100553 727156759
2131262825 1312534322
854807795 1416630482
1824427145 2106736666
1606578453 1293016133
243821753 1394250038
2123044134 1860509249
1373702635 1202130057
1663839713 227430318
138694259 1998915562
1168141881 622419759
56571600 1795344024
714019527 763280955
147182853 527417493
843106862 30282563
757439322 1031396969
196447644 862207415
131354249 741218499
700471518 1051255439
196787924 1955781395
1202547785 159566323
2020075573 440609677
1642739735 1178108272
1405538590 1246294560
1097726474 1159095800
1781515560 1544232850
1192093226 118384708
881665663 1838087160
218021005 1906112753
1936395316 1028848516
2060245486 1061127867
1923335283 546350991
1287569490 109209482
1160464921 2054689532
1862987279 1988041008
123684 1357252846
1797862523 918051417
2096159689 2020199257
1119010169 1293118610
304730763 1354214631
750963833 69252995
187637703 2086246323
1776849835 1943057060
1701686165 1069303366
2098151883 1994870841
908515060 1490597834
2036948825 2010913721
2120123203 684366695
591572580 1177034667
1017592028 1133104476
342873674 307076211
1225127628 1017715712
890431321 2140736198
1286371160 1173803669
380534653 2009441490
2078694485 1591101923
1529864598 1131498486
927071898 118848541
1188151907 1159230786
1006617979 481274416
1971872250 1138820142

Output from my AC program:

Code: Select all

5238.583
1877.591
24981.545
4085.842
11531.560
24368.904
26367.187
23113.484
24469.133
11711.895
4904.623
12149.970
9533.015
9126.438
5741.861
20423.329
15961.865
21645.840
5026.889
20383.915
17634.784
11710.172
21510.874
1082.736
34506.503
5552.027
5543.981
11171.397
5659.382
15188.698
10726.980
21679.774
5472.443
11477.426
19272.148
2247.924
25619.083
873.500
11268.028
21815.116
13450.721
7389.745
6376.253
15791.183
18860.475
5676.812
9012.308
28017.767
32735.324
12836.534
30188.803
10645.953
9890.516
21992.819
8371.470
16976.533
17084.560
12974.263
27086.088
19433.295
25891.998
8313.991
13659.072
15246.561
30031.074
21739.613
13602.525
32096.692
11828.328
11968.044
29307.837
24016.447
10958.394
5139.852
35039.012
13306.052
9738.037
13009.051
17490.692
16831.330
27867.377
25055.216
12142.959
17306.282
13840.247
16021.950
23604.212
22496.794
3380.942
4946.822
6855.535
15806.811
28269.749
27834.457
6661.357
10334.363
18680.431
3492.703
20253.612
17587.106

[fizzlesticks]

Thanks, about 5 of my outputs are .001 less than they should be. Hate these kind of problems.

edit: Got AC, had the height of the triangle stored in a double as sqrt(.75), had to change it to a long double.

[SS_HASAN]

My code gives perfect result to uDebug and the above test cases brianfry mentioned earlier.Still I'm getting WA. Can't figure it out. Please help me.
Code Removed after Accepted

[brianfry713]

If you use double instead of long double and submit in C++ you will get AC.

[SS_HASAN]

brianfry713 Thank you so much. My grateful gratitude to you (y)