Задача о точках на прямой

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.
Руководители: к.ф-м.н., профессор Пирогов Владислав Юрьевич, ник - Vladislav_133; к.п.н, доцент Слинкин Дмитрий Анатольевич, ник - xdsl

Модераторы: xdsl, Vladislav_133

Задача о точках на прямой

Сообщение Vladislav_133 06 апр 2014, 15:30

Задача о прямой линии, как ни странно на первый взгляд, вызвала определенные затруднения. Задача стоила всего одно очко, но из 10 решавших ее, только одному участнику удалось написать программу, которая проходит все тесты. Не правда ли, это должно заинтриговать любознательного программиста? Вот и я по началу был заинтригован, но загадка разрешилась быстро. Вот программа, которую я использовал для проверки тестов. Именно проверки, потому-что сами тесты я составлял исходя их расчетов в электронных таблицах.
Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int  main(){
    int i=2,k;
    double x1,y1,x2,y2,x3,y3,a,b;
    k=scanf("%lf %lf",&x1,&y1);
    if(k==-1)return 1;
    k=scanf("%lf %lf",&x2,&y2);
    if(k==-1)return 1;
    while(scanf("%lf %lf",&x3,&y3)!=-1){
              a=(x3-x1)*(y2-y1);
              b=(y3-y1)*(x2-x1);
              a=a-b;
              if(a<0)a=(-1)*a;
              if(a<=0.0001)i++;
              else break;
   }
    printf("%d\n",i);
    return 0;
}


Обратите внимание, что все вычисления я произвожу в 64-битовых вещественных числах (double, lf), а не 32-битовых вещественных числах (float, f). Если произвести замену (double, lf) -> (float, f), то вот тогда мы и получим программу, которая будет проходить только часть тестов - приблизительно половину. Вот и ответ на вопрос, почему почти ни у кого программа правильно не работает. Не привыкли задумываться о точности вычислений. Остается ответить на вопрос: "Почему тесты, которые программы не проходили, у разных авторов не всегда совпадали?". В действительности совпадения как раз были, а у некоторых участников, из разных городов было полное совпадение. Так вот, полное совпадение было у тех участников, которые писали программу на одном и том же языке, с использованием одних и тех же библиотек. У тех же участников, которые писали программу на разных языках, совпадение не пройденных тестов было только частичным.

Ну вот, по этой программе все. Может быть есть что и участникам сказать?
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1