On my PC this code outputs 1 9 3 for test№15. But in codeforce another output Here is my submition: http://codeforces.net/contest/618/submission/15669012 I think this is because of doubles, but I'm not sure. Could smb point my mistake, please?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
On my PC this code outputs 1 9 3 for test№15. But in codeforce another output Here is my submition: http://codeforces.net/contest/618/submission/15669012 I think this is because of doubles, but I'm not sure. Could smb point my mistake, please?
Name |
---|
Need sort with struct, like this
Never ever use Heron's formula for calculating triangle's area in competitive programming. I have not heard about a single occurence when it can be useful. Especially do not use it if the resulting area can be small (say, zero). Heron's formula is very sensitive to precision in that matter, and
long double
s probably won't help you there. Say, when c = 2a = 2b, semi-circumference is equal to c = 2a, then formula becomes p(p - a)(p - b)(p - c) ≈ 2a·(2a - a)·(2a - 2a)·(2a - 2a) ≈ 4a3(a - a), and even a small precision error (like 10 - 11) in the last factor leads to huge error in the total because of the big factor in the beginning.So, yes, it's precision error. Your program genuinely thinks that that triangle is non-degenerate.
Use cross product instead: area of triangle (0, 0) – (x1, y1) – (x2, y2) is |x1y2 - x2y1|. There is only one subtraction (and that's the bad guy who spoils precision the most) and you do not multiply that error by another factors.
Got it. Thanks a lot!