Я из команды SUrSU 1.
Не понятно, что у вас за тесты на эту задачу.
Говорится, что координаты даны с точностью до 5 знаков, мы предполагали, что достаточно точно.
Посылали с большой точностью на контесте, это было в самом конце контеста, как-то не успели подумать, что можно и с маленькой точностью послать, к тому же еще были заняты написанием задачи И.
Теперь я написал такое же решение, посылал с точностью 10^-6 вроде - не принималась, 10^-2 - принялась.
Что за бред????

Мда, это все конечно интересно, но мое решение например вообще нигде не использует точность и AC c первого раза. Но правда и задача очень специфическая.

Все верно, если входные данные зашумлены на 1E-5, то требовать от решения 1E-6 неверно

Это у нас используется для проверки коэффициента подобия.
1E-4 -  8WA
1E-3 - 44WA
Все-таки странно.
Почему именно 1E-2 проходит, а 1E-3 - плохая точность.

Посчитаем погрешность вычисления коэффициента подобия: погрешность координат 1e-5, значит, погрешность расстояния — 3e-5, погрешность коэффициента при максимальном стократном отношении размеров — 3e-3.
Понятно, что точности 1e-3 недостаточно для сравнения коэффициентов подобия.

Edited by author 01.11.2006 17:41

Что-то я не совсем понимаю это.
У нас есть эталонная доминошка со стороной 1. Координаты на ней точные. 1<=K<=100. Любые доминошки, с меньшими расстояниями не подходят.
Рассматриваем доминошки с большими расстояниями, они вроде бы, по логике, должны быть более точно засняты. Получается, что чем крупнее снимок, тем хуже точность, странно.
По-моему у крупного снимка относительная точность больше, те с ростом коэффициента точность растет.
Или я не прав?

I tried to follow the topic but the translator russian - english was not enough. I have a program which gets WA in test 44. Actually I proved changing precision issues and the best I got was WA in test 90, so I think the only bug in the code is about precision.
The function that deals with precision in my code is:

bool check(par *q, double t) {
  int i, j, orden[12];
  bool usado[12];
  memset(usado, 0, sizeof(usado));
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) if (!usado[j])
      if (dist(q[i].first - p[j].first, q[i].second - p[j].second) < eps) break;
    if (j == n) return false;
    usado[j] = true;
  }
  return true;
}

Array p keeps the input points and array q the points in a possible domino tile. The function check returns if the points in both arrays are "more or less" the same

The function dist is:
double dist(double x, double y) {
  return fabs(x)+ fabs(y);
}

and the eps is defined to be 1e-3

It would be great if anybody who got AC explains how he dealt with precision in his code

This is not precision problem, but wrong approach problem.

Input coordinates do not define points. They define a SET of points whose precise coordinates become input values after rounding. E.g. pair (1.2345;6.7890) defines half-open square [1.23445;1.23455) x [6.78895;6.78905). All points within this square become (1.2345;6.7890) after rounding.

You task is to find all dies with 1<=L<=100 whose precise dot coordinates fall into these half-open squares with one-to-one relationship.