Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 46, средняя оценка - 4.70
Bogdand
3 / 3 / 12
Регистрация: 04.12.2010
Сообщений: 93
#1

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

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

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

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

http://www.cyberforum.ru/cpp-beginners/thread861522.html
Входной файл 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 Алгоритм на изображение... Просто проверяется условие существование треугольника!
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2012, 20:31
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Пересечение двух окружностей (C++):

Задача на пересечение двух окружностей
Всем привет! Прошу вашей помощи в решении задачи так как я уже дней пять над...

Пересечение двух прямых и проверка на пересечение
Доброго времени суток слизал функцию проверки...

Столкновение двух окружностей
Итак,я сталкиваю два шарика(но вообще их больше,массив). Какое-то время после...

Координаты пересечения двух окружностей
На вход даются целочисленные координаты двух окружностей и целочисленные их...

Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк.
Добавить в строковый класс функцию, которая создает строку, содержащую...

16
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 20:40 #2
не учли, как минимум, что они могут совпадать. тогда условие треугольника не верно, а пересечение имеется
0
Bogdand
3 / 3 / 12
Регистрация: 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;
    }
0
Thinker
01.10.2012, 20:43
  #4

Не по теме:

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

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

Не по теме:

Опоздал ><

0
Nixy
ComfyMobile
400 / 281 / 34
Регистрация: 24.07.2012
Сообщений: 916
01.10.2012, 20:56 #10
Цитата Сообщение от Bogdand Посмотреть сообщение
на сайте с заданием

Не по теме:

а что за сайт?



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

Не по теме:

Опоздал ><

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

Не по теме:

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

0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 21:01 #13
Цитата Сообщение от Bogdand Посмотреть сообщение
второе условие как я с квадратами сравню?
легко, нужно условие без корня только для граничных случаев, если они не верны, дальше с корнем
0
Nixy
ComfyMobile
400 / 281 / 34
Регистрация: 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
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
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 = западло.
Но вот что нужно еще (что считается "настоящим" пересечением) - не пойму ;-)
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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;
}
все прошло )
1
Toshkarik
1148 / 865 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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";
1
01.10.2012, 21:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2012, 21:30
Привет! Вот еще темы с решениями:

Вводится значение двух радиусов окружностей
Помогите создать блок схему для задачи c пояснениями пожалуйста: Вводится...

Вычислить площадь пересечения двух окружностей
Здравствуйте) Может кто-нибудь сталкивался с написнием программы для вычисления...

Найти точку соприкосновения двух окружностей
Как можно найти точку соприкосновения двух окружностей, если заданы их...

Пересечение двух многоугольников
Имеются два многоугольника, например два пятиугольника, координаты заданны...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru