Страница 1 из 1

Задача Круги

СообщениеДобавлено: 24 мар 2016, 11:13
Vladislav_133
Задача Круги

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

СообщениеДобавлено: 24 мар 2016, 15:02
hardcore_test
Могут ли совпадать точки?

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

СообщениеДобавлено: 24 мар 2016, 15:11
Vladislav_133
Совпадающие точки? Нет, мы считаем их одной точкой, если вдруг они появятся в списке.

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

СообщениеДобавлено: 24 мар 2016, 15:12
Vladislav_133
В задаче есть одна неоднозначность. Я на ней внимание не акцентировал. И в тестах ее не будет. Обсудим это уже на разборе. :)

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

СообщениеДобавлено: 24 мар 2016, 15:34
hardcore_test
Это случайно не точки лежащие на одной прямой?

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

СообщениеДобавлено: 24 мар 2016, 15:53
Vladislav_133
Угадали :)
В тексте есть на указание.

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

СообщениеДобавлено: 24 мар 2016, 16:44
hardcore_test
Критично ли для этой задачи вместо 0 выводить -0?

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

СообщениеДобавлено: 24 мар 2016, 17:18
Vladislav_133
ну это ваша программа. однако 0 = -0

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

СообщениеДобавлено: 24 мар 2016, 17:33
hardcore_test
Я в том плане будет ли засчитано если к примеру для примера в условии будет вывод 4 -0 -0 2?

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

СообщениеДобавлено: 24 мар 2016, 17:43
Vladislav_133
Да. Но 4 -0 <=> 4 0, это две окружности с одинаковыми координатами, со всеми вытекающими отсюда последствиями.

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

то это будет ошибка - не прохождение конкретного теста

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

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

Дело в том, что имеем дело с вещественными числами. И вот возникает парадокс. Возьмем три точки: (2,0), (-2,0), (0,0). Они лежат на одной прямой. При переборе мы сразу отбросим эти точки. Т.е. они изначально не войдут в тройки, для которых мы строим окружность. Однако. Вот представьте, что центр окружности лежит в точке (0,500). Посчитаем расстояние от центра до точки (0,2). Получим что-то около 500.004. Т.е. с точности до сотых все три точки оказываются на одной окружности. Понимая это я не использовал тестов, которые бы привели к таким противоречиям. Но, если уж ставить задачу по всем правилам, надо такие варианты было также учитывать в решении.

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

СообщениеДобавлено: 27 мар 2016, 16:15
hardcore_test
Интересен алгоритм нахождения центра окружности по 3 точкам, кто каким пользовался?

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

СообщениеДобавлено: 27 мар 2016, 16:25
Reconix
hardcore_test писал(а):Интересен алгоритм нахождения центра окружности по 3 точкам, кто каким пользовался?


Я систему из двух уравнений с двумя неизвестными методом Крамера решал. В нем автоматом отбрасывались точки, лежащие на одной прямой.

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

СообщениеДобавлено: 28 мар 2016, 16:22
hardcore_test
Чем 0 отличается от -0

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

СообщениеДобавлено: 28 мар 2016, 16:26
hardcore_test
С этой задачей забавно получилось, так как я не видел и все еще не вижу с математической точки зрения разницу между 0 и -0, то -0 я превращал в 0, но еще более забавная ошибка, вместо того что бы просто сравнивать до 2 знака после запятой, я округлял. В результате верно решенная задача из-за не правильного вывода получит мало баллов

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

СообщениеДобавлено: 28 мар 2016, 17:07
Vladislav_133
да там нет разницы. и я на это внимание не обращаю.

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

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

Прочитав это утверждение я написал условие: если такой Х раньше встречался и такой У раньше встречался, то эти данные мы не читаем.
Соответственно если до этого был вход 0 2 затем 2 0, а потом поступит 2 2. То моя программа координату 2 2 отбросит эта ошибка и стала роковой из-за которой потерял ровно половину тестов и как я понимаю 1 место

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

СообщениеДобавлено: 29 мар 2016, 20:51
Vladislav_133
у вашего основного соперника тоже не все просто :)

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

СообщениеДобавлено: 29 мар 2016, 21:01
Reconix
Да, ошибки есть... И за них больше стыдно :D

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

СообщениеДобавлено: 20 апр 2016, 11:52
Vladislav_133
Задача о кругах. Общий алгоритм я уже обсуждал

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка 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;
}