Поиск оптимального кольца

Question

Помогите пожалуйста с решением задания. На вход из файла поступает N-ное количество значений x,y и значение r. Задание состоит в том, чтобы найти координаты точек, являющихся вершинами фигуры Кольцо внутри которой будет лежать наибольшее количество точек.В моем случае вершиной фигуры будет являться центр кольца. Необходимо исключить повторяющиеся точки и вывести координаты вершины x;y при которой в фигуре будет лежать наибольшее количество точек.

1)На данный момент у меня есть:

1.значение r

2.заполненный массив с координатами x

3.заполненный массив с координатами y

также количество точек x и y было уравнено, так что точки x;y будут попарно составлять одну отчку в нашей системе координат

условие для проверки принадлежности точек к фигуре я представил так:

1)сначал смещаем координаты x y, вычитая из них координаты вершины

далее идет проверка условия:

данный фрагмент кода работает некорректно, помогите пожалуйста разобраться с причиной или найти альтернативное решение:

float x0;
float y0;
float x1;
float y1;
int k;
int e=0;
float otvet_x;
float otvet_y;

for (int i{};i<a;i++)
{
 x0=*(x+i);
 y0=*(y+i);
    for (int j{};j<a;j++)
    {
      x1=*(x+j);
      y1=*(y+j);

      x1=fabs(x1)-fabs(x0);
      y1=fabs(y1)-fabs(y0);
        if ((x1 || y1)>0)
        {
         if ( ((x1*x1+y1*y1)>=r*r)&&((x1*x1+y1*y1)<=((2*r)*(2*r))) )
            k=0;
            k++;
        }
    }
    if (k>e) e=k;
    otvet_x=*(x+i);
    otvet_y=*(y+i);
}
cout<<"При вершине кольца с координатами: x="<<otvet_x<<" y="<<otvet_y;
cout<<" фигура будет содержать наибольше количество точек:"<<e;
cout<<" при радиусе= "<<r<<endl;

Answer 1

Ну, тогда ваш переборный код должен иметь примерно такой вид (не компилировал, мог и очепятаться...):

int count = -1, idx = -1;

for(int i = 0; i < a; ++i)
{
    int in = 0;
    for(int j = 0; j < a; ++j)
    {
        double dist = (x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);
        if (dist > r*r && dist < 4*r*r) in++;
    }
    if (in > count)
    {
        idx = i;
        count = in;
    }
}

cout << idx << "  " << count;

Можно немного оптимизировать, типа, вычислять r*r заранее, но, думаю, оптимизатор тоже справится :) Возиться и выбрасывать центральную точку - не вижу смысла, ну, посчитает ее разок...

БЛОГ НА HUSL

Поиск оптимального кольца

Ответы (1 шт):