## 10233 - Dermuba Triangle

Moderator: Board moderators

### 10233 - Dermuba Triangle

Hi,

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

Thanks for any help.
yaro
New poster

Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

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

Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

### 10233 GIVE ME ANY idea.

hi,
everybody ples give any idea of this problem.
i don't understand.
ples help me.
''I want to be most laziest person in the world''
turcse143
Learning poster

Posts: 81
Joined: Wed May 09, 2007 9:59 pm

### Re: 10233 - Dermuba Triangle

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.
stcheung
Experienced poster

Posts: 114
Joined: Mon Nov 18, 2002 6:48 am

### Re: 10233 - Dermuba Triangle

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?
jenovaforum
New poster

Posts: 2
Joined: Sun Feb 14, 2010 12:05 am

### Re: 10233 - Dermuba Triangle

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.
fizzlesticks
New poster

Posts: 2
Joined: Wed May 02, 2012 10:10 am

### Re: 10233 - Dermuba Triangle

Random input:
Code: Select all
`511588181 6526572281852756952 17908659631140952686 1363183732085991715 17269611451881899363 1978701405561122256 1959090857988078148 15103337181711549392 9556330732006051356 10133061902140695990 10754916371261436914 16941187441157750383 7188514241671851593 895934864660080930 13095098771158971203 7540890091406746237 20075026841650884999 16705593841806877757 1112019542691497039 644354038475571795 17453858241556993033 4259127541936246473 10366940511992327124 3975875331410893723 1500312217428320206 18508948321397529928 14041060652122957489 1689757121438208337 4077966631717306541 1647325435253930796 1098289268958308304 728794096251869832 1660677033625212927 4617096561106063694 20587475891656649765 13167099671742622721 1581635489470845892 10661591501463746684 1531385546884214116 31568936919100553 7271567592131262825 1312534322854807795 14166304821824427145 21067366661606578453 1293016133243821753 13942500382123044134 18605092491373702635 12021300571663839713 227430318138694259 19989155621168141881 62241975956571600 1795344024714019527 763280955147182853 527417493843106862 30282563757439322 1031396969196447644 862207415131354249 741218499700471518 1051255439196787924 19557813951202547785 1595663232020075573 4406096771642739735 11781082721405538590 12462945601097726474 11590958001781515560 15442328501192093226 118384708881665663 1838087160218021005 19061127531936395316 10288485162060245486 10611278671923335283 5463509911287569490 1092094821160464921 20546895321862987279 1988041008123684 13572528461797862523 9180514172096159689 20201992571119010169 1293118610304730763 1354214631750963833 69252995187637703 20862463231776849835 19430570601701686165 10693033662098151883 1994870841908515060 14905978342036948825 20109137212120123203 684366695591572580 11770346671017592028 1133104476342873674 3070762111225127628 1017715712890431321 21407361981286371160 1173803669380534653 20094414902078694485 15911019231529864598 1131498486927071898 1188485411188151907 11592307861006617979 4812744161971872250 1138820142`

Output from my AC program:
Code: Select all
`5238.5831877.59124981.5454085.84211531.56024368.90426367.18723113.48424469.13311711.8954904.62312149.9709533.0159126.4385741.86120423.32915961.86521645.8405026.88920383.91517634.78411710.17221510.8741082.73634506.5035552.0275543.98111171.3975659.38215188.69810726.98021679.7745472.44311477.42619272.1482247.92425619.083873.50011268.02821815.11613450.7217389.7456376.25315791.18318860.4755676.8129012.30828017.76732735.32412836.53430188.80310645.9539890.51621992.8198371.47016976.53317084.56012974.26327086.08819433.29525891.9988313.99113659.07215246.56130031.07421739.61313602.52532096.69211828.32811968.04429307.83724016.44710958.3945139.85235039.01213306.0529738.03713009.05117490.69216831.33027867.37725055.21612142.95917306.28213840.24716021.95023604.21222496.7943380.9424946.8226855.53515806.81128269.74927834.4576661.35710334.36318680.4313492.70320253.61217587.106`
brianfry713
Guru

Posts: 1768
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10233 - Dermuba Triangle

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.
fizzlesticks
New poster

Posts: 2
Joined: Wed May 02, 2012 10:10 am