Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.70
Bogdand
 Аватар для Bogdand
3 / 3 / 0
Регистрация: 04.12.2010
Сообщений: 93
#1

Пересечение двух окружностей - C++

01.10.2012, 20:31. Просмотров 5953. Ответов 16
Метки нет (Все метки)

На плоскости даны две окружности. Требуется проверить, пересекаются ли они.

Входные данные

Входной файл INPUT.TXT состоит из двух строк. На каждой строке записана информация об одной окружности – координаты ее центра x и y (целые числа, по модулю не превосходящие 5000) и радиус (целое число 1 ≤ r ≤ 1000).

Выходные данные

В выходной файл OUTPUT.TXT выведите «YES», если окружности пересекаются, и «NO» в противном случае.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
    double x1,x2,y1,y2,r1,r2;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin >> x1 >> x2 >> y1 >> y2 >> r1 >> r2;
    double r = sqrt(pow(x2 - x1,2) + pow(y2 - y1,2)); //расстояние между центрами
    // проверка на совпадение 2-ух окружностей
    if (r == 0 && r1 == r2)
    {
        cout << "YES";
        return 0;
    }
 
    if (r1 + r2 >= r && r1 + r >= r2 && r2 + r >= r1)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}
существует какой то контрпример, при котором задача не проходит, я его не знаю но таковой имеется, поскольку система проверки меня не пропускает, что же я не учёл?
PS Алгоритм на изображение... Просто проверяется условие существование треугольника!
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2012, 20:31     Пересечение двух окружностей
Посмотрите здесь:

C++ Пересечение двух многоугольников
C++ Вычислить площадь пересечения двух окружностей
Пересечение двух кругов C++
Вводится значение двух радиусов окружностей C++
C++ Пересечение двух окружностей
Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк. C++
C++ Найти пересечение двух массивов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4218 / 2192 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 20:40     Пересечение двух окружностей #2
не учли, как минимум, что они могут совпадать. тогда условие треугольника не верно, а пересечение имеется
Bogdand
 Аватар для Bogdand
3 / 3 / 0
Регистрация: 04.12.2010
Сообщений: 93
01.10.2012, 20:41  [ТС]     Пересечение двух окружностей #3
Цитата Сообщение от Thinker Посмотреть сообщение
не учли, как минимум, что они могут совпадать
C++
1
2
3
4
5
6
// проверка на совпадение 2-ух окружностей
    if (r == 0 && r1 == r2)
    {
        cout << "YES";
        return 0;
    }
Thinker
01.10.2012, 20:43
  #4

Не по теме:

ну да, не заметил

I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
01.10.2012, 20:51     Пересечение двух окружностей #5
Может дело в погрешности из-за извлечения корня и прямого сравнения даблов?
Уберите корень и сравнивайте квадраты
Nixy
ComfyMobile
 Аватар для Nixy
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
01.10.2012, 20:53     Пересечение двух окружностей #6
чот я не понял в чом проблема? программа ведь работает?
Bogdand
 Аватар для Bogdand
3 / 3 / 0
Регистрация: 04.12.2010
Сообщений: 93
01.10.2012, 20:55  [ТС]     Пересечение двух окружностей #7
Цитата Сообщение от Nixy Посмотреть сообщение
чот я не понял в чом проблема? программа ведь работает?
да, но на сайте с заданием не проходит на втором тесте (Wrong Answer)
Thinker
Эксперт C++
 Аватар для Thinker
4218 / 2192 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 20:55     Пересечение двух окружностей #8
может и правда в погрешности, так как имеются граничные случаи (вырожденного в отрезок треугольника), когда окружности касаются (одна внутри другой и одна вне другой). там для радиусов должно выполнено r = r1+r2 либо r1 = r + r2 в зависимости от того, как они касаются. при погрешностях условие алгоритма в этих случаях может нарушится
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
01.10.2012, 20:55     Пересечение двух окружностей #9
Bogdand, возможно дело в погрешности. Не вычисляйте корень, сравнивайте с r * r.

Не по теме:

Опоздал ><

Nixy
ComfyMobile
 Аватар для Nixy
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
01.10.2012, 20:56     Пересечение двух окружностей #10
Цитата Сообщение от Bogdand Посмотреть сообщение
на сайте с заданием

Не по теме:

а что за сайт?



Цитата Сообщение от I.M. Посмотреть сообщение
Уберите корень и сравнивайте квадраты
дельная идея
Bogdand
 Аватар для Bogdand
3 / 3 / 0
Регистрация: 04.12.2010
Сообщений: 93
01.10.2012, 20:59  [ТС]     Пересечение двух окружностей #11
Цитата Сообщение от Toshkarik Посмотреть сообщение
Bogdand, возможно дело в погрешности. Не вычисляйте корень, сравнивайте с r * r.

Не по теме:

Опоздал ><

второе условие как я с квадратами сравню?
Nixy
01.10.2012, 21:01
  #12

Не по теме:

написал не подумав

Thinker
Эксперт C++
 Аватар для Thinker
4218 / 2192 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 21:01     Пересечение двух окружностей #13
Цитата Сообщение от Bogdand Посмотреть сообщение
второе условие как я с квадратами сравню?
легко, нужно условие без корня только для граничных случаев, если они не верны, дальше с корнем
Nixy
ComfyMobile
 Аватар для Nixy
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
01.10.2012, 21:08     Пересечение двух окружностей #14
C++
1
if (r1*r1 + r2*r2+2*r1*r2 >= r )
это вот случай если у тебя они касаются в одной точке воде так
где r=(x1-x2)^2+(y1-y2)^2
Igor3D
850 / 436 / 38
Регистрация: 01.10.2012
Сообщений: 2,208
01.10.2012, 21:14     Пересечение двух окружностей #15
Невнятно сформулирована задача. Проверить окружности изолированы просто

#define SQR(a) ((a) * (a)) // или template
bool outside = SQR(r1 + r2) > SQR(x2 - x1) + SQR(y2 - y1);

Конечно вызовы pow и sqrt = западло.
Но вот что нужно еще (что считается "настоящим" пересечением) - не пойму ;-)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
01.10.2012, 21:23     Пересечение двух окружностей #16
Цитата Сообщение от Bogdand Посмотреть сообщение
также абсолютно не проходит!
даже странно. когда-то решал так:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <math.h>
int main(){
  int a, b, r, a1, b1, r1;
  double temp;
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  scanf("%d%d%d%d%d%d", &a, &b, &r, &a1, &b1, &r1);
  temp=sqrt(pow((double)(a-a1), 2.) + pow((double)(b-b1), 2.));
  if(temp>(double)(r+r1) || temp+(double)r<r1 || temp+(double)r1<r)
        printf("NO");
  else
      printf("YES");
 
  return 0;
}
все прошло )
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2012, 21:30     Пересечение двух окружностей
Еще ссылки по теме:

C++ Определить количество точек пересечения двух окружностей
Столкновение двух окружностей C++
Найти точку соприкосновения двух окружностей C++
C++ Координаты пересечения двух окружностей
Задача на пересечение двух окружностей C++

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

Или воспользуйтесь поиском по форуму:
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
01.10.2012, 21:30     Пересечение двух окружностей #17
Зашел только что на ********, эта задача у меня пройдена вот так:
C++
1
2
3
4
5
6
   d = ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 );
   
   if ( d <= ( r1 + r2 ) * ( r1 + r2 ) && d >= ( r1 > r2 ? r1 - r2 : r2 - r1 ))
      outFile << "YES";
   else
      outFile << "NO";
Yandex
Объявления
01.10.2012, 21:30     Пересечение двух окружностей
Ответ Создать тему
Опции темы

Текущее время: 02:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru