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

@Bogdand · Регистрация: 04.12.2010

Author24 — интернет-сервис помощи студентам

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

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

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

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

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

C++

#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 · 01.10.2012, 20:40

не учли, как минимум, что они могут совпадать. тогда условие треугольника не верно, а пересечение имеется

@Bogdand · 01.10.2012, 20:41 **[ТС]**

Сообщение от Thinker

не учли, как минимум, что они могут совпадать

C++

// проверка на совпадение 2-ух окружностей
    if (r == 0 && r1 == r2)
    {
        cout << "YES";
        return 0;
    }

@Thinker · 01.10.2012, 20:43

Не по теме:

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

@I.M. · 01.10.2012, 20:51

Может дело в погрешности из-за извлечения корня и прямого сравнения даблов?
Уберите корень и сравнивайте квадраты

@Nixy · 01.10.2012, 20:53

чот я не понял в чом проблема? программа ведь работает?

@Bogdand · 01.10.2012, 20:55 **[ТС]**

Сообщение от Nixy

чот я не понял в чом проблема? программа ведь работает?

да, но на сайте с заданием не проходит на втором тесте (Wrong Answer)

@Thinker · 01.10.2012, 20:55

может и правда в погрешности, так как имеются граничные случаи (вырожденного в отрезок треугольника), когда окружности касаются (одна внутри другой и одна вне другой). там для радиусов должно выполнено r = r1+r2 либо r1 = r + r2 в зависимости от того, как они касаются. при погрешностях условие алгоритма в этих случаях может нарушится

@Toshkarik · 01.10.2012, 20:55

Bogdand, возможно дело в погрешности. Не вычисляйте корень, сравнивайте с r * r.

Не по теме:

Опоздал ><

@Nixy · 01.10.2012, 20:56

Сообщение от Bogdand

на сайте с заданием

Не по теме:

а что за сайт?

Сообщение от I.M.

Уберите корень и сравнивайте квадраты

дельная идея

@Bogdand · 01.10.2012, 20:59 **[ТС]**

Сообщение от Toshkarik

Bogdand, возможно дело в погрешности. Не вычисляйте корень, сравнивайте с r * r.

Не по теме:

Опоздал ><

второе условие как я с квадратами сравню?

@Nixy · 01.10.2012, 21:01

Не по теме:

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

@Thinker · 01.10.2012, 21:01

Сообщение от Bogdand

второе условие как я с квадратами сравню?

легко, нужно условие без корня только для граничных случаев, если они не верны, дальше с корнем

@Nixy · 01.10.2012, 21:08

C++

1	if (r1r1 + r2r2+2r1r2 >= r )

это вот случай если у тебя они касаются в одной точке воде так
где r=(x1-x2)^2+(y1-y2)^2

@Igor3D · 01.10.2012, 21:14

Невнятно сформулирована задача. Проверить окружности изолированы просто

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

Конечно вызовы pow и sqrt = западло.
Но вот что нужно еще (что считается "настоящим" пересечением) - не пойму ;-)

valeriikozlov · 01.10.2012, 21:23

Сообщение от Bogdand

также абсолютно не проходит!

даже странно. когда-то решал так:

C

#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;
}

все прошло )

@Toshkarik · 01.10.2012, 21:30

Зашел только что на acmp.ru, эта задача у меня пройдена вот так:

C++

   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";

@Bogdand 4 / 4 / 0 Регистрация: 04.12.2010 Сообщений: 93
	01.10.2012, 20:59 [ТС]	11
	Сообщение от Toshkarik Bogdand, возможно дело в погрешности. Не вычисляйте корень, сравнивайте с r * r. Не по теме: Опоздал >< второе условие как я с квадратами сравню? 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	01.10.2012, 21:01	13
	Сообщение от Bogdand второе условие как я с квадратами сравню? легко, нужно условие без корня только для граничных случаев, если они не верны, дальше с корнем 0

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,746
	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

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	01.10.2012, 20:40	2
	не учли, как минимум, что они могут совпадать. тогда условие треугольника не верно, а пересечение имеется 0

@Thinker
	01.10.2012, 20:43 #4
	Не по теме: ну да, не заметил 0

@I.M. 576 / 559 / 47 Регистрация: 16.12.2011 Сообщений: 1,389
	01.10.2012, 20:51	5
	Может дело в погрешности из-за извлечения корня и прямого сравнения даблов? Уберите корень и сравнивайте квадраты 0

@Nixy ComfyMobile 401 / 282 / 34 Регистрация: 24.07.2012 Сообщений: 916
	01.10.2012, 20:53	6
	чот я не понял в чом проблема? программа ведь работает? 0

@Bogdand 4 / 4 / 0 Регистрация: 04.12.2010 Сообщений: 93
	01.10.2012, 20:55 [ТС]	7
	Сообщение от Nixy чот я не понял в чом проблема? программа ведь работает? да, но на сайте с заданием не проходит на втором тесте (Wrong Answer) 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	01.10.2012, 20:55	8
	может и правда в погрешности, так как имеются граничные случаи (вырожденного в отрезок треугольника), когда окружности касаются (одна внутри другой и одна вне другой). там для радиусов должно выполнено r = r1+r2 либо r1 = r + r2 в зависимости от того, как они касаются. при погрешностях условие алгоритма в этих случаях может нарушится 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	01.10.2012, 20:55	9
	Bogdand, возможно дело в погрешности. Не вычисляйте корень, сравнивайте с r * r. Не по теме: Опоздал >< 0

@Nixy ComfyMobile 401 / 282 / 34 Регистрация: 24.07.2012 Сообщений: 916
	01.10.2012, 20:56	10
	Сообщение от Bogdand на сайте с заданием Не по теме: а что за сайт? Сообщение от I.M. Уберите корень и сравнивайте квадраты дельная идея 0

@Nixy
	01.10.2012, 21:01 #12
	Не по теме: написал не подумав 0