Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.60/146: Рейтинг темы: голосов - 146, средняя оценка - 4.60
-14 / 7 / 4
Регистрация: 24.02.2013
Сообщений: 234
1

Найти количество точек с целочисленными координатами, которые попадают внутрь заданной окружности, либо лежат на границе

29.11.2014, 20:02. Показов 26392. Ответов 34
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задана окружность радиуса R с центром в точке (X,Y). Необходимо определить количество точек с целочисленными координатами, которые попадают внутрь этой окружности, либо лежат на границе.

Входные данные: три целых числа через пробел - X,Y,R. X,Y не превышает 10^9 по своему абсолютному значению. 1 <= R <= 1000.

Выходные данные: единственное число - количество точек внутри окружности.

Пример входных данных
0 0 2

Пример выходных данных
13

никак не могу осилить.

Добавлено через 15 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "stdafx.h"
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    string temp;
    string Input;
    int Result;
 
    getline(cin, Input);
 
    for (int i = Input.length() - 1; Input[i] != ' '; i--)//считываем радиус в обратном порядке их строки ввода
    {
        temp += Input[i];
    }
    Input.clear();
    for (int i = temp.length()-1; i >=0; i--)//преобразовываем радиус в нормальный порядок
    {
        Input += temp[i];
    }
    Result = atoi(Input.c_str());//радиус в инте
 
    Result = (Result * 2) - 1;//кол-во точек на линии если ее провести горизонтально через центр окр Radius*2+1,а если отнять от этого выражения -2(не считаем точки через которые проведена окр) то получится кол-во точек внутри окр на этой горизонтали.
    cout << (Result*Result + 4);//получается что горизонталь == стороне вписанного в окр квадрата,значит если ее возвести в квадрат то получится количество всех точек внутри этой окр,и прибавляем 4 точки через которые проведена окр.
    /*getchar();
    getchar();*/
    return 0;
}
Тестил на куче примеров все норм пробую через онлайн ошибка в тестах.Получается что для этой задачи х и у избыточные данные?или я где-то ошибся?
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
29.11.2014, 20:02
Ответы с готовыми решениями:

Определить, сколько точек с целочисленными координатами попадают в круг заданного радиуса с центром в начале координат
Вводится радиус круга R. Определить, сколько точек с целочисленными координатами попадают в круг...

Найти количество точек с целочисленными координатами внутри заданного отрезка
как мне найти количество точек с целочисленными координатами внутри отрезка. Вам даны начальные...

Найти количество точек с целочисленными координатами, попадающих в круг заданного радиуса с центром в начале координат
Вычислить количество точек с целочисленными координатами, попадающих в круг радиуса R (R&gt;0) с...

Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н
Я подумала, что нужно будет написать класс Point. Немного написала, и остановилась на методе,...

34
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
29.11.2014, 21:10 2
ardos, да просто перебери все точки лежащие внутри описанного квадрата и проверь для каждой, лежит ли она внутри или на границе или нет.

и зачем считывать строчку? почему бы не считать три числа? даже в одну переменную?

C++ (Qt)
1
cin >> r >> r >> r;
2
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
29.11.2014, 22:28 3
Цитата Сообщение от SlavaSSU Посмотреть сообщение
и зачем
первые 2 числа?
Цитата Сообщение от SlavaSSU Посмотреть сообщение
почему бы не
забить на них вообще?
1
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
29.11.2014, 23:12 4
_Ivana, так я не предлагаю ими пользоваться. задача - даны 3 числа, записанные через пробел. получите третье число.

что быстрее: считывать стрингом и че-то там делать или считать три инта в одну переменную и результат будет тот же?

Добавлено через 1 минуту
_Ivana, или ты имеешь в виду можно сразу третье число как-то прочитать и все?
1
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
29.11.2014, 23:25 5
_Ivana, координаты центра не нужно знать, только радиус, так как X и Y все равно целые числа
Если еще учесть что R не больше 1000, задачу можно даже не оптимизировать, но мы ведь не такие...
1
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
29.11.2014, 23:27 6
SlavaSSU, нет, я конечно выберу ваш вариант чтения трех чисел в одну переменную, просто я лишь отметил независимость ответа от координат центра, но потом прочитал топик и понял, что это и так всем было очевидно.

Добавлено через 42 секунды
D_in_practice, спасибо, КЭП, я это и имел в виду
1
Модератор
Эксперт по электронике
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
29.11.2014, 23:29 7
Цитата Сообщение от ardos Посмотреть сообщение
единственное число - количество точек внутри окружности.
сдается мне здесь просто площадь нужно подсчитать
и округлить
Цитата Сообщение от ardos Посмотреть сообщение
Пример входных данных
0 0 2
Пример выходных данных
13
2*2*3.14=12.56
1
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
29.11.2014, 23:34 8
ValeryS, идея интересная, при больших радиусах может и будет работать, надо проверять. Но при единичном радиусе 5 мы никаким округлением не получим, к примеру.

Добавлено через 1 минуту
Цитата Сообщение от D_in_practice Посмотреть сообщение
но мы ведь не такие
правильно, ValeryS уже предложил интересную идею, я пытался пару минут подумать над другой, но она не реализовалась в алгоритм и я переключился на другую задачку
1
Модератор
Эксперт по электронике
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
29.11.2014, 23:39 9
Цитата Сообщение от _Ivana Посмотреть сообщение
Но при единичном радиусе 5 мы никаким округлением не получим,
действительно не получим это я не додумал
нужно еще покумекать

Добавлено через 1 минуту
а вот интересно при нулевом радиусе будет результат 1(одна точка центр) или 0 ?
1
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
29.11.2014, 23:42 10
Хрен с ним, если это не будет работать только для 1-цы - можно исключение явно прописать. У меня нет уверенности, что это будет работать для любых других радиусов. И это я еще молчу про ограниченную точность даблов и заданного числа пи...

Добавлено через 2 минуты
Цитата Сообщение от ValeryS Посмотреть сообщение
а вот интересно при нулевом радиусе будет результат 1(одна точка центр) или 0 ?
Если "продолжать по непрерывности" (хотя тут наоборот разрывность ), то при радиусе 0 должна быть одна точка. При -1 или 3 или -3, по вкусу определения.
1
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
29.11.2014, 23:47 11
Пока увидел след закономерность и сразу видно что не подходит вычисление площади.
Код
R       N        delta
1       1           -
2       3^2         8 = 9 - 1
3       5^2         16 = 25 - 9
4       7^2 - 4     20 = 45 -25
5       9^2 - 12    24 = 69 - 45
1
Модератор
Эксперт по электронике
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
29.11.2014, 23:53 12
Цитата Сообщение от _Ivana Посмотреть сообщение
При -1
так радиус не может быть отрицательным если отрицательный значит рисуем в другую сторону

Добавлено через 1 минуту
D_in_practice,
извини, не понял твою таблицу
N это количество точек?
но при радиусе 1 точек то пять
2
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
30.11.2014, 01:07 13
Придумал алгоритм, наваял его (только не бейте, просто сегодня настроение ваять на Haskell ), там же наваял лобовой подсчет, оба алгоритма разумеется целочисленные, результаты совпадают, мой прожевывает числа порядка 10^6 за пару-тройку секунд (на Си будет гораааздо быстрее), лобовой задумывается уже на 10^3. Алгоритм начинает с верхней точки (координаты 0,r) "бежит по кромке" вправо, если следующая клетка внутри - бежим на нее, если снаружи - прыгаем вниз и плюсуем предыдущую x-координату (количество точек в линии) к аккумулятору. Заканчиваем, когда y-координита стала равна 0. В конце добавляем r к аккумулятору, умножаем на 4 четвертинки окружности и плюсуем центральную клетку. На Си перевести - полминуты.
Haskell
1
2
3
4
5
6
7
8
9
10
11
rez r = go 0 r 0 where
    go _ 0 a = (a+r)*4+1
    go x y a = if (x+1)^2+y^2<=r^2 then go (x+1) y a else go x (y-1) (a+x)
 
rez' r = length [(x,y) | x<-[-r..r], y<-[-r..r], x^2+y^2<=r^2]
 
main = do
    putStr $ unlines.map (\r->show r++" - "++show (rez r)++" - "++show (rez' r)) $ [1..100]
    print $ rez 1000
    print $ rez' 1000
    print $ rez 1000000
1
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
30.11.2014, 01:18 14
ardos,
Для малого R <= 1000 годится решение в лоб
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
 
int main(){
    
    int R;
    std::cin >> R >> R >> R;
 
    int N = 0;
    for (int x = 0; x <= 2*R; ++x)
        for (int y = 0; y <= 2*R; ++y)
            if ((x-R)*(x-R) + (y-R)*(y-R) <= R*R)
                ++N;
                
    std::cout << N << std::endl;
}

Здесь видно, что Ваш алгоритм не работает
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <iomanip>
 
int main(){
    
    for (int R = 1; R <= 100; ++R){     
        int n = 0;
        for (int x = 0; x <= 2*R; ++x)
            for (int y = 0; y <= 2*R; ++y)
                if ((x-R)*(x-R) + (y-R)*(y-R) <= R*R)
                    ++n;
                
        std::cout << std::setw(3) << R << std::setw(7) << n
                  << std::setw(7) << (2*R - 1)*(2*R - 1) + 4 << std::endl;
    }
}
Название: Безымянный.jpg
Просмотров: 404

Размер: 16.3 Кб

Используя Вашу идею привожу оптимизированный алгоритм
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
int main(){
    
    int R;
    std::cin >> R >> R >> R;
 
    int N = 0;
    int x = R;
    for (int y = 1; y <= R; ++y){
        while(x*x + y*y > R*R)
            --x;
        N += 2*x + 1;
    }
                    
    std::cout << 2*N + 2*R + 1 << std::endl;
}

_Ivana, это не Ваш алгоритм но идея та же, ТС пытался ее осуществить
2
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
30.11.2014, 01:25 15
D_in_practice, да, все об одном Только я бы не надеялся на умность оптимизирующего Сишного компилятора и сам в явном виде раз и навсегда рассчитал бы ему R^2 в отдельную переменную.
2
343 / 343 / 331
Регистрация: 02.10.2014
Сообщений: 666
30.11.2014, 01:26 16
10^6 доли секунды считает, больше нельзя зацикливается (числа большие)
1
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 30
30.11.2014, 01:30 17
ЗЫ собственно, мы повторили один из алгоритмов заливки произвольного контура, не самый плохой, кстати.

Добавлено через 2 минуты
Не понял, почему больше 10^6 нельзя. Лонг лонгами их задать и все, R^2 = 10^12 вполне влезет. А у меня на Haskell безграничная длинная арифметика задаром на борту, но зато скорость меньше
1
Модератор
Эксперт по электронике
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
30.11.2014, 10:00 18
короче опять я, со своими площадями
нарисовал на бумажке и понял простую вещь
нужно считать площадь вписанного квадрата и прибавить количество точек на окружности которые не попадают в квадрат
сторона вписанного квадрата равна 2*R-1
точек на окружности 4
пока это все эмпирически
проверьте
R
0 (2*0-1)*(2*0-1)+0(окружности нет)=1
1 (2*1-1)*(2*1-1)+4=5
2 (2*2-1)*(2*2-1)+4=13
3 (2*3-1)*(2*4-1)+4=29
4 (2*4-1)*(2*4-1)+4=53

Добавлено через 3 минуты
Цитата Сообщение от ardos Посмотреть сообщение
Result = (Result * 2) - 1;//кол-во точек на линии если ее провести горизонтально через центр окр Radius*2+1,а если отнять от этого выражения -2(не считаем точки через которые проведена окр) то получится кол-во точек внутри окр на этой горизонтали.
cout << (Result*Result + 4);//получается что горизонталь == стороне вписанного в окр квадрата,значит если ее возвести в квадрат то получится количество всех точек внутри этой окр,и прибавляем 4 точки через которые проведена окр.
вроде тоже самое

Добавлено через 31 минуту
по правильному сторона квадрата равна радиусу умноженному на корень из двух
значит площадь удвоенный квадрат радиуса
но здесь я запутался с округлениями
сторону округлять или площадь?
Код
 
радиус   сторона   площадь сторона по предыдущей формуле   площадь по предыдущей формуле
 1        1.41        2                     1                               1
 2        2.82        8                     3                               9
 3        4.23        18                    5                              25
 4        5,64        32                    7                              49
в общем еще покумекаю, вечером отпишусь
1
Модератор
Эксперт по электронике
8951 / 6717 / 921
Регистрация: 14.02.2011
Сообщений: 23,714
03.12.2014, 23:15 19
А все таки я её добил
и через площадь
правда площадь считал длинной отрезков при целочисленных x
отрезок получается (x.-y)-(x,y) длинна его 2*y+1
как пришел к этому решению долго рассказывать
при помощи бумажки циркуля и линейки
вписанный квадрат при радиусе больше трех получается многоугольником
главный затык был как подсчитать площадь
пока не понял что площадь можно подсчитать отрезками

вот программа правда совершенно не оптимизирована, интерес пропал

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <math.h>
 
int func1(int r)
{
 int count=0;
 for(int i=-r;i<=r;i++)
  for(int j=-r;j<=r;j++)
      if((i*i+j*j)<=(r*r))
          count++;
 return count;
 
 
}
int func2(int r)
{
int count=0;
for(int x=r;x>=-r;x--) // десь можно уменьшить в два раза подсчитывая полукгруг
 {
  int y=(int)sqrt((double)(r*r)-(double)(x*x)); //подсчитываем y по теореме Пифагора
   // корень долгая операция как убыстрить не знаю
  count+=2*y+1;
 }
 
return count;
}
 
 
int main(void) {
for(int n=0;n<100;n++)
{
int S=(int)(n*n*3.14);
printf("%d\t",n);
printf("  %d \t",func1(n));
printf("  %d \t",func2(n));
printf(" %d \n",S+1);
 
}
    return 0;
}
func1 тупое вычисление попадания точек берется описаный квадрат ((r,r),(-r,-r))
и проверяется по точкам попали или нет
func2 моя функция
результаты совпадают

при цикле от 10000 до 20000 func2 отрабатывает секунд за десять
func1 умирает
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
03.12.2014, 23:33 20
ValeryS, если не хочется вычислять корень, то можно наоборот найти такой наибольший Y, что Y * Y <= r * r - x * x;
0
03.12.2014, 23:33
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
03.12.2014, 23:33
Помогаю со студенческими работами здесь

Вычислить количество точек с целочисленными координатами, принадлежащих кругу
Вычислить k - количество точек с целочисленными координатами, принадлежащих кругу радиуса R (R&gt; 0)...

Вычислить количество точек с целочисленными координатами, находящихся в круге
вычислите количество точек с целочисленными координатами,находящиеся в круге радиуса R (R&gt;0)

Вывести количество точек, которые находятся внутри окружности либо на ее границе
Вводится x0,y0,r,n Координаты n точак x0,y0-центр окружности r-радиус n-количество точак...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Как работать с ветками (branch) в Git
InfoMaster 17.01.2025
Система контроля версий Git произвела революцию в процессе разработки программного обеспечения, предоставив разработчикам мощный инструмент для управления изменениями в коде. Одной из наиболее важных. . .
Как откатить последние коммиты в Git
InfoMaster 17.01.2025
Система контроля версий Git стала неотъемлемой частью современной разработки программного обеспечения, предоставляя разработчикам мощные инструменты для управления изменениями в коде. Одним из. . .
Что такое boilerplate и scaffold, чем они отличаются
InfoMaster 17.01.2025
В современном мире разработки программного обеспечения эффективность и скорость создания качественного кода играют crucial роль в успехе проектов. Разработчики постоянно ищут способы оптимизировать. . .
Чем отличаются ссылки и указатели в С++
InfoMaster 17.01.2025
В современном программировании на C++ эффективная работа с памятью является ключевым аспектом разработки качественного программного обеспечения. Указатели и ссылки представляют собой два. . .
В чем разница между PUT и POST
InfoMaster 17.01.2025
В современной веб-разработке правильное использование HTTP-методов играет ключевую роль в создании надежных и эффективных API-интерфейсов. Протокол HTTP прошел долгий путь развития с момента своего. . .
DTO, POCO и Value Object: что это такое, когда и как использовать
InfoMaster 17.01.2025
Введение в паттерны передачи данных В современной разработке программного обеспечения эффективное управление данными и их передача между различными слоями приложения являются ключевыми аспектами. . .
Что такое pull request в Git
InfoMaster 17.01.2025
В современной разработке программного обеспечения pull request в Git представляет собой ключевой механизм для эффективного взаимодействия между разработчиками при работе над общим кодом проекта. По. . .
Как вернуться к предыдущему коммиту в Git
InfoMaster 17.01.2025
Система контроля версий Git представляет собой мощный инструмент для управления изменениями в программном коде, который позволяет разработчикам эффективно отслеживать и контролировать историю. . .
Что такое паттерны программировани­я и проектирования
InfoMaster 17.01.2025
Роль паттернов в современной разработке программного обеспечения В современном мире разработки программного обеспечения паттерны проектирования стали неотъемлемой частью профессионального подхода. . .
Как добавить конструктор Яндекс Карт на сайт
InfoMaster 17.01.2025
Введение в API Яндекс Карт В современной веб-разработке интеграция картографических сервисов стала неотъемлемой частью многих проектов. API Яндекс Карт представляет собой мощный инструмент для. . .
Что такое javascript:void­­(0) и зачем это нужно
InfoMaster 17.01.2025
Когда вы сталкиваетесь с веб-разработкой, особенно с использованием JavaScript, одной из директив, которая часто встречается, является javascript:void(0). Это выражение вызывает интерес из-за своей. . .
Что такое оркестрация и хореография микросервисов
InfoMaster 17.01.2025
Введение в оркестрацию и хореографию микросервисов В современном мире разработки программного обеспечения микросервисная архитектура стала ключевым подходом к созданию масштабируемых и гибких. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru