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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.70
Bogdand
 Аватар для Bogdand
3 / 3 / 0
Регистрация: 04.12.2010
Сообщений: 93
01.10.2012, 20:31     Пересечение двух окружностей #1
На плоскости даны две окружности. Требуется проверить, пересекаются ли они.

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

Входной файл 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 Алгоритм на изображение... Просто проверяется условие существование треугольника!
Изображения
 
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 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
399 / 280 / 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
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 20:55     Пересечение двух окружностей #8
может и правда в погрешности, так как имеются граничные случаи (вырожденного в отрезок треугольника), когда окружности касаются (одна внутри другой и одна вне другой). там для радиусов должно выполнено r = r1+r2 либо r1 = r + r2 в зависимости от того, как они касаются. при погрешностях условие алгоритма в этих случаях может нарушится
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
01.10.2012, 20:55     Пересечение двух окружностей #9
Bogdand, возможно дело в погрешности. Не вычисляйте корень, сравнивайте с r * r.

Не по теме:

Опоздал ><

Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 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
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 21:01     Пересечение двух окружностей #13
Цитата Сообщение от Bogdand Посмотреть сообщение
второе условие как я с квадратами сравню?
легко, нужно условие без корня только для граничных случаев, если они не верны, дальше с корнем
Nixy
ComfyMobile
 Аватар для Nixy
399 / 280 / 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
793 / 410 / 33
Регистрация: 01.10.2012
Сообщений: 2,070
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
4660 / 2486 / 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++ Определить количество точек пересечения двух окружностей

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

Или воспользуйтесь поиском по форуму:
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 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     Пересечение двух окружностей
Ответ Создать тему
Опции темы

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