1

Помогите пожалуйста с решением задания. На вход из файла поступает 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;
11
  • данный фрагмент кода работает некорректно – с этого момента поподробнее, пожалуйста. Что должен делать данный фрагмент и что он делает сейчас? В чём именно проблема?
    – V-Mor
    22 дек 2020 в 5:00
  • 1
    "вершиной фигуры будет являться центр кольца" - это бред?
    – user176262
    22 дек 2020 в 5:07
  • 1
    Зачем в этих выражениях fabs - x1=fabs(x1)-fabs(x0);?
    – user176262
    22 дек 2020 в 5:17
  • 1
    ... и что делает эта проверка if ((x1 || y1)>0)?
    – user176262
    22 дек 2020 в 5:18
  • 1
    ... и почему обнуляется k?
    – user176262
    22 дек 2020 в 5:20

1 ответ 1

3

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

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 заранее, но, думаю, оптимизатор тоже справится :) Возиться и выбрасывать центральную точку - не вижу смысла, ну, посчитает ее разок...

7
  • Добрый день, больше спасибо за ответ. Не совсем понимаю как работает ваш алгоритм
    – eternal
    22 дек 2020 в 10:36
  • Просто полный перебор. Поочередно беру точку в качестве центральной, и смотрю, сколько точек попадает в кольцо (квадрат расстояния от r^2 до 4r^2. Запоминаю текущий максимум. Все.
    – Harry
    22 дек 2020 в 11:12
  • Я не совсем понял if и что происходит в нем, нам ведь надо вывести координаты x и y
    – eternal
    22 дек 2020 в 11:32
  • Если количество точек в кольце для данной центральной точки превышает ранее достигнутый максимум - запоминаем новый максимум и индекс точки. Координаты выводите под конец как x[idx] и y[idx].
    – Harry
    22 дек 2020 в 13:38
  • не понимаю, почему то все равно некорректно работает....
    – eternal
    22 дек 2020 в 17:04

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.