Задача Круги

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.

Задача Круги

Сообщение Vladislav_133 24 мар 2016, 11:13

Задача Круги
Вложения
Krugi.pdf
(255.58 Кб) Скачиваний: 305
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Круги

Сообщение hardcore_test 24 мар 2016, 15:02

Могут ли совпадать точки?
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение Vladislav_133 24 мар 2016, 15:11

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

Re: Задача Круги

Сообщение Vladislav_133 24 мар 2016, 15:12

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

Re: Задача Круги

Сообщение hardcore_test 24 мар 2016, 15:34

Это случайно не точки лежащие на одной прямой?
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение Vladislav_133 24 мар 2016, 15:53

Угадали :)
В тексте есть на указание.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Круги

Сообщение hardcore_test 24 мар 2016, 16:44

Критично ли для этой задачи вместо 0 выводить -0?
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение Vladislav_133 24 мар 2016, 17:18

ну это ваша программа. однако 0 = -0
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Круги

Сообщение hardcore_test 24 мар 2016, 17:33

Я в том плане будет ли засчитано если к примеру для примера в условии будет вывод 4 -0 -0 2?
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение Vladislav_133 24 мар 2016, 17:43

Да. Но 4 -0 <=> 4 0, это две окружности с одинаковыми координатами, со всеми вытекающими отсюда последствиями.

Т.е. если ваша программа скажем выдаст
4 -0 3
4 0 3

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

Re: Задача Круги

Сообщение Vladislav_133 27 мар 2016, 15:53

Данная задача решается следующим образом. Надо вспомнить из геометрии тот факт, что через три точки, не лежащих на одной прямой на плоскости можно всегда провести окружность.
Таким образом надо написать следующий алгоритм. Выбрать все возможные тройки из множества точек (количество сочетаний из n по 3), вычислить параметры окружности для этих трех точек, а за тем подставлять координаты остальных точек, чтобы проверить не лежат ли они на данной окружности. В принципе это все, но.

Дело в том, что имеем дело с вещественными числами. И вот возникает парадокс. Возьмем три точки: (2,0), (-2,0), (0,0). Они лежат на одной прямой. При переборе мы сразу отбросим эти точки. Т.е. они изначально не войдут в тройки, для которых мы строим окружность. Однако. Вот представьте, что центр окружности лежит в точке (0,500). Посчитаем расстояние от центра до точки (0,2). Получим что-то около 500.004. Т.е. с точности до сотых все три точки оказываются на одной окружности. Понимая это я не использовал тестов, которые бы привели к таким противоречиям. Но, если уж ставить задачу по всем правилам, надо такие варианты было также учитывать в решении.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Круги

Сообщение hardcore_test 27 мар 2016, 16:15

Интересен алгоритм нахождения центра окружности по 3 точкам, кто каким пользовался?
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение Reconix 27 мар 2016, 16:25

hardcore_test писал(а):Интересен алгоритм нахождения центра окружности по 3 точкам, кто каким пользовался?


Я систему из двух уравнений с двумя неизвестными методом Крамера решал. В нем автоматом отбрасывались точки, лежащие на одной прямой.
Reconix
 
Сообщения: 9
Зарегистрирован: 31 мар 2014, 22:33
Полное имя: Мосин В. С.

Re: Задача Круги

Сообщение hardcore_test 28 мар 2016, 16:22

Чем 0 отличается от -0
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение hardcore_test 28 мар 2016, 16:26

С этой задачей забавно получилось, так как я не видел и все еще не вижу с математической точки зрения разницу между 0 и -0, то -0 я превращал в 0, но еще более забавная ошибка, вместо того что бы просто сравнивать до 2 знака после запятой, я округлял. В результате верно решенная задача из-за не правильного вывода получит мало баллов
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение Vladislav_133 28 мар 2016, 17:07

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

Re: Задача Круги

Сообщение hardcore_test 29 мар 2016, 20:48

В задаче такая глупая ошибка, что стыдно о ней рассказывать:
Vladislav_133 писал(а):Совпадающие точки? Нет, мы считаем их одной точкой, если вдруг они появятся в списке.

Прочитав это утверждение я написал условие: если такой Х раньше встречался и такой У раньше встречался, то эти данные мы не читаем.
Соответственно если до этого был вход 0 2 затем 2 0, а потом поступит 2 2. То моя программа координату 2 2 отбросит эта ошибка и стала роковой из-за которой потерял ровно половину тестов и как я понимаю 1 место
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача Круги

Сообщение Vladislav_133 29 мар 2016, 20:51

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

Re: Задача Круги

Сообщение Reconix 29 мар 2016, 21:01

Да, ошибки есть... И за них больше стыдно :D
Reconix
 
Сообщения: 9
Зарегистрирован: 31 мар 2014, 22:33
Полное имя: Мосин В. С.

Re: Задача Круги

Сообщение Vladislav_133 20 апр 2016, 11:52

Задача о кругах. Общий алгоритм я уже обсуждал

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
//circumcircles
#include <math.h>
#include <stdio.h>

int getg(double, double, double, double, double, double, double * , double * , double * );

int main(){
    double x[1000], y[1000];
    double xxx[1000], yyy[1000], rrr[1000];
    double xx,yy,rr,dr;
    int n=0,i,j,k,l,m1,m2=0,m=0,nn=0,p=0;
    while(scanf("%lf %lf",&x[n],&y[n])!=EOF){
        for(i=0;i<n;i++)if(x[i]==x[n]&&y[i]==y[n])break;
        if(i==n)n++;
    }
    if(n<3) return 1;
    for(i=0; i<n-2; i++){
        for(j=i+1; j<n-1; j++){
            for(k=j+1; k<n; k++){
                if(!getg(x[i],y[i],x[j],y[j],x[k],y[k],&xx,&yy,&rr)){
                    m1=0;p=1;
                    for(l=0; l<n; l++){
                        if(l==i||l==j||l==k)continue;
                        dr = sqrt((xx-x[l])*(xx-x[l])+(yy-y[l])*(yy-y[l]));
                        if(fabs(dr-rr)<=0.01){
                            m1++;
                            if(m1>m)m=m1;
                        }  
                    }                          
                }
            }
        }
    }
    if(!p)return 1;
    printf("%d\n",m+3);
    for(i=0; i<n-2; i++){
        for(j=i+1; j<n-1; j++){
            for(k=j+1; k<n; k++){
                if(!getg(x[i],y[i],x[j],y[j],x[k],y[k],&xx,&yy,&rr)){
                    m1=0;
                    for(l=0; l<n; l++){
                        if(l==i||l==j||l==k)continue;
                        dr = sqrt((xx-x[l])*(xx-x[l])+(yy-y[l])*(yy-y[l]));
                        if(fabs(dr-rr)<=0.01){
                            m1++;
                        }  
                    }
                    //
                    if(m1==m){
                        for(l=0; l<nn; l++){
                            if(fabs(xx-xxx[l])<=0.01&&fabs(yy-yyy[l])<=0.01&&fabs(rrr[l]-rr)<=0.01)break;
                        }                      
                        if(l==nn){
                            xxx[nn]=xx; yyy[nn]=yy; rrr[nn]=rr; nn++;
                        }
                    }                          
                }
            }
        }
    }
    for(l=0; l<nn; l++){
        printf("%lf %lf %lf\n",xxx[l],yyy[l],rrr[l]);
    }
    return 0;
}
//get circumcircle's parameters on three points
int getg(double xx1, double yy1, double xx2, double yy2, double xx3, double yy3, double * xx, double * yy, double * rr){
    double p,a1,b1,c1,a2,b2,c2;
    double x1,x2,x3,y1,y2,y3,x4,y4,x5,y5,x6,y6,r6;
    x1 = xx1; x2 = xx2; x3 = xx3; y1 = yy1; y2 = yy2; y3 = yy3;
    //
    p = (x1-x3)*(y2-y3)-(x2-x3)*(y1-y3);
    if(!p)return -1;
    //
    x4=(x1+x2)/2; y4=(y1+y2)/2; x5=(x1+x3)/2; y5=(y1+y3)/2;
    a1=x2-x1; b1=y2-y1; c1=x4*(x2-x1)+y4*(y2-y1);
    a2=x3-x1; b2=y3-y1; c2=x5*(x3-x1)+y5*(y3-y1);
    //
    x6=(c1*b2-c2*b1)/(a1*b2-a2*b1);
    y6=(a1*c2-a2*c1)/(a1*b2-a2*b1);
    r6=(x1-x6)*(x1-x6)+(y1-y6)*(y1-y6);
    r6=sqrt(r6);
    *xx=x6; *yy=y6; *rr=r6;
    //    
    return 0;
}

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


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

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

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

cron