Блог пользователя dilshodp

Автор dilshodp, 9 лет назад, По-русски

On my PC this code outputs 1 9 3 for test№15. But in codeforce another output Here is my submition: http://codeforces.me/contest/618/submission/15669012 I think this is because of doubles, but I'm not sure. Could smb point my mistake, please?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Need sort with struct, like this

Struct Pair {
int first, second;
int p; // position
} ab[100001];
bool cmp(Pair l, Pair r) {
return (l.first < r.first || (l.first == r.first && l.second < r.second));
}
int main {

SI(n);
forin(i, 0, n)
{
SII(ab[i].first, ab[i].second);
ab[i].p = i;
}

.......

return 0;
}

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 doubles 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.