ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1509. Domino Recognition

Что за тесты?
Posted by AndreySUrSU 31 Oct 2006 23:24
Я из команды SUrSU 1.
Не понятно, что у вас за тесты на эту задачу.
Говорится, что координаты даны с точностью до 5 знаков, мы предполагали, что достаточно точно.
Посылали с большой точностью на контесте, это было в самом конце контеста, как-то не успели подумать, что можно и с маленькой точностью послать, к тому же еще были заняты написанием задачи И.
Теперь я написал такое же решение, посылал с точностью 10^-6 вроде - не принималась, 10^-2 - принялась.
Что за бред????
Re: Что за тесты?
Posted by Nechaev Ilya (Rybinsk SAAT) 1 Nov 2006 03:43
Мда, это все конечно интересно, но мое решение например вообще нигде не использует точность и AC c первого раза. Но правда и задача очень специфическая.
Re: Что за тесты?
Posted by Ivankov Dmitry 1 Nov 2006 09:58
Все верно, если входные данные зашумлены на 1E-5, то требовать от решения 1E-6 неверно
Re: Что за тесты?
Posted by AndreySUrSU 1 Nov 2006 10:27
Это у нас используется для проверки коэффициента подобия.
1E-4 -  8WA
1E-3 - 44WA
Все-таки странно.
Почему именно 1E-2 проходит, а 1E-3 - плохая точность.
Re: Что за тесты?
Posted by Vladimir Yakovlev (USU) 1 Nov 2006 12:05
Посчитаем погрешность вычисления коэффициента подобия: погрешность координат 1e-5, значит, погрешность расстояния — 3e-5, погрешность коэффициента при максимальном стократном отношении размеров — 3e-3.
Понятно, что точности 1e-3 недостаточно для сравнения коэффициентов подобия.
Re: Что за тесты?
Posted by Nechaev Ilya (Rybinsk SAAT) 1 Nov 2006 17:39


Edited by author 01.11.2006 17:41
Re: Что за тесты?
Posted by AndreySUrSU 1 Nov 2006 20:48
Что-то я не совсем понимаю это.
У нас есть эталонная доминошка со стороной 1. Координаты на ней точные. 1<=K<=100. Любые доминошки, с меньшими расстояниями не подходят.
Рассматриваем доминошки с большими расстояниями, они вроде бы, по логике, должны быть более точно засняты. Получается, что чем крупнее снимок, тем хуже точность, странно.
По-моему у крупного снимка относительная точность больше, те с ростом коэффициента точность растет.
Или я не прав?
Re: Что за тесты?
Posted by ucmcauchy 2 Nov 2006 21:15
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
Re: Что за тесты?
Posted by Denis Koshman 31 Aug 2008 08:59
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.