e-olimp 197. Отрезок и окружности

27/09/2018 by Антон Джашимов

Задача

На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны $1,2,3\dots.$ Также на плоскости задан отрезок, концы которого находятся в точках $(X_{1}, Y_{1})$ и $(X_{2}, Y_{2}).$ Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

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

Первая строка входного файла содержит 4 целых числа $X_{1}, Y_{1}, X_{2}, Y_{2}.$ Эти числа не превосходят $10^{3}$ по абсолютной величине. Заданный отрезок имеет ненулевую длину.

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

В выходной файл выведите ответ на задачу.

Тесты

Входные данные	Выходные данные
-1 -1 1 1	2
-1 1 1 1	1
1 1 2 1	1
-5 -5 5 -5	5
-10 10 -10 10	28

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws java.lang.Exception {
        final double e = 10e-8;
        Scanner in = new Scanner(System.in);
        double x1, y1, x2, y2;
        x1 = in .nextDouble();
        y1 = in .nextDouble();
        x2 = in .nextDouble();
        y2 = in .nextDouble();
        double d, a, b;
        d = Math.abs((y2 * x1 - x2 * y1) / Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
        //Растояние до точки на отрезке, ближайщей к началу координат
        a = Math.sqrt(x1 * x1 + y1 * y1);
        //Растояние от начала координат до первой точки
        b = Math.sqrt(x2 * x2 + y2 * y2);
        //Растояние от начала координат до второй точки
        int count = 0;
        if ((2 * x1 * x1 - 2 * x1 * x2 + 2 * y1 * y1 - 2 * y1 * y2 < 0) | (2 * x2 * x2 - 2 * x1 * x2 + 2 * y2 * y2 - 2 * y1 * y2 < 0))
            //проверка первого условия
            count = (int)(Math.max(a, b) + e) - (int)(Math.min(a, b) - e);
        else {
            //второе условие
            count = (int)(a + e) - (int)(d - e);
            count = count + (int)(b + e) - (int)(d - e);
            if ((Math.abs(Math.round(d) - d) < e) & (Math.abs(d) > e)) {
                //проверка крайнего случая
                count--;
            }
        }
        System.out.print(count);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main(String[] args) throws java.lang.Exception {

final double e = 10e-8;

Scanner in = new Scanner(System.in);

double x1, y1, x2, y2;

x1 = in .nextDouble();

y1 = in .nextDouble();

x2 = in .nextDouble();

y2 = in .nextDouble();

double d, a, b;

d = Math.abs((y2 * x1 - x2 * y1) / Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));

//Растояние до точки на отрезке, ближайщей к началу координат

a = Math.sqrt(x1 * x1 + y1 * y1);

//Растояние от начала координат до первой точки

b = Math.sqrt(x2 * x2 + y2 * y2);

//Растояние от начала координат до второй точки

int count = 0;

if ((2 * x1 * x1 - 2 * x1 * x2 + 2 * y1 * y1 - 2 * y1 * y2 < 0) | (2 * x2 * x2 - 2 * x1 * x2 + 2 * y2 * y2 - 2 * y1 * y2 < 0))

//проверка первого условия

count = (int)(Math.max(a, b) + e) - (int)(Math.min(a, b) - e);

else {

//второе условие

count = (int)(a + e) - (int)(d - e);

count = count + (int)(b + e) - (int)(d - e);

if ((Math.abs(Math.round(d) - d) < e) & (Math.abs(d) > e)) {

//проверка крайнего случая

count--;

}

System.out.print(count);

}

Решение

Для начала рассмотрим первое условие. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до начала координат возрастает. Для такого отрезка ответ очевиден — это количество целых чисел между расстояниями от начала координат до обоих концов отрезка. Условие из шестнадцатой строчки кода получилось путем приведения подобных и раскрытия скобок следующих неравенств: $x_{1}^{2}+y_{1}^{2}-x_{2}^{2}-y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0$ и $-x_{1}^{2}-y_{1}^{2}+x_{2}^{2}+y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0.$

Иначе сведем данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к $(0,0)$ точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее. Также мы добавляем маленькую константу
$\varepsilon = 10^{-8}$ к большему расстоянию до конца отрезка и отнимаем из меньшего, чтобы избежать случая нахождения какой-либо точки отрезка на окружности. В противном случае решение задачи будет работать не корректно.

Ссылки

Условие задачи на e-olymp
Код решения

ML 24

26/11/2017 by Мазурин Эдвард

Условие задачи:

Треугольник задан длинами сторон. Найти радиус вписанной и описанной окружностей.

Тесты:


3	4	5	1	2.5
7.5	10	13	2.45012	6.52361
1	3	4	0	inf
1	1	3	Не существует!	Не существует!

Код программы:

import java.util.*;

public class triangle {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Введите a: ");
        double a = in.nextDouble();
        System.out.print("Введите b: ");
        double b = in.nextDouble();
        System.out.print("Введите c: ");
        double c = in.nextDouble();
            double p = (a + b + c) / 2;
            double S = Math.sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона
            double r = S / p;
            double R = a * b * c / (4 * S);
            System.out.println("Радиус вписанной окружности равен " + r);
            System.out.println("Радиус описанной окружности равен " + R);
    }
}

import java.util.*;

public class triangle {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.print("Введите a: ");

double a = in.nextDouble();

System.out.print("Введите b: ");

double b = in.nextDouble();

System.out.print("Введите c: ");

double c = in.nextDouble();

double p = (a + b + c) / 2;

double S = Math.sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона

double r = S / p;

double R = a * b * c / (4 * S);

System.out.println("Радиус вписанной окружности равен " + r);

System.out.println("Радиус описанной окружности равен " + R);

}

Алгоритм:

Проводим следующие вычисления (порядок сохранен):

double p = (a + b + c) / 2;
double S = Math.sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона
double r = S / p;
double R = a * b * c / (4 * S);
System.out.println("Радиус вписанной окружности равен " + r);
System.out.println("Радиус описанной окружности равен " + R);

double p = (a + b + c) / 2;

double S = Math.sqrt(p * (p - a) * (p - b) * (p - c)); //формула Герона

double r = S / p;

double R = a * b * c / (4 * S);

System.out.println("Радиус вписанной окружности равен " + r);

System.out.println("Радиус описанной окружности равен " + R);

Вычисляем полупериметр треугольника: $[latex]p[/latex] = [latex]\frac{a + b + c}{2}[/latex]$
Находим площадь по формуле Герона: $[latex]S[/latex] = [latex]\sqrt{p(p-a)(p-b)(p-c)}[/latex]$
Вычисляем радиус вписанной окружности по формуле: $[latex]r[/latex] = [latex]\frac{S}{p}[/latex]$
Вычисляем радиус описанной окружности по формуле: $[latex]R[/latex] = [latex]\frac{abc}{4S}[/latex]$

Работающая версия программы на Ideone.com

Ссылка на источник

e-olymp 4. Two circles

01/07/2016 by Владислав Козачков

Задача взята с сайта e-olymp.com.

Условие

Определить количество точек пересечения двух окружностей.

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

Шесть чисел: x1, y1, r1, x2, y2, r2, где x1, y1, x2, y2 — координаты центров окружностей, а r1, r2 — их радиусы. Все числа — действительные, не превышают 10⁹, заданы не более чем с тремя знаками после запятой.

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

Количество точек пересечения. Если точек пересечения бесконечно много, то вывести -1.

Тесты:

X₁	Y₁	R₁	X₂	Y₂	R₂	N
0	0	5	5	0	1	2
0	0	5	0	0	6	1
0	1	6	0	3	6	2

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scan = new Scanner(System.in);
		double x1 = scan.nextDouble(), y1 = scan.nextDouble(), r1 = scan.nextDouble();
		double x2 = scan.nextDouble(), y2 = scan.nextDouble(), r2 = scan.nextDouble();
		double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
		double rads = r1 + r2;
		if (range == 0 && r1 == r2) {
			System.out.print(-1);
		}
		else if (range == rads || range + r1 == r2 || range + r2 == r1) {
			System.out.print(1);
		}
		else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){
			System.out.print(0);
		}
		else {
			System.out.print(2);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

double x1 = scan.nextDouble(), y1 = scan.nextDouble(), r1 = scan.nextDouble();

double x2 = scan.nextDouble(), y2 = scan.nextDouble(), r2 = scan.nextDouble();

double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

double rads = r1 + r2;

if (range == 0 && r1 == r2) {

System.out.print(-1);

}

else if (range == rads || range + r1 == r2 || range + r2 == r1) {

System.out.print(1);

}

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){

System.out.print(0);

}

else {

System.out.print(2);

}

Ход решения:

Высчитываем расстояние между центрами окружностей по формуле: $Range$ = $\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2}$ . Вычисление в одну строку:

double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

1	double range = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

Далее рассчитываем суму радиусов окружностей.
Если центры совпадают (Range = 0) и длины радиусов равны, значит, совпадают и окружности:

if (range == 0 && r1 == r2) {
	System.out.print(-1);
}

if (range == 0 && r1 == r2) {

System.out.print(-1);

}

Если расстояние между окружностями равно сумме радиусов, окружности имеют одну общую точку, касаясь друг друга снаружи. Также одна из окружностей может лежать внутри другой и касаться ее изнутри:

else if (range == rads || range + r1 == r2 || range + r2 == r1) {
	System.out.print(1);
}

else if (range == rads || range + r1 == r2 || range + r2 == r1) {

System.out.print(1);

}

Если расстояние между окружностями превышает сумму радиусов, это значит, что они не пересекаются. Также одна окружность может лежать внутри другой, но не касаться ее:

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){
	System.out.print(0);
}

else if ((range > rads) || ((range < rads) && ((range * 2 < r1 && range + r2 < r1) || (range * 2 < r2 && range + r1 < r2)))){

System.out.print(0);

}

В остальных случаях окружности пересекаются и имеют две общие точки:

else {
	System.out.print(2);
}

else {

System.out.print(2);

}

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: окружности

e-olimp 197. Отрезок и окружности

Задача

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

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

Тесты

Код программы

Решение

Ссылки

ML 24

e-olymp 4. Two circles

Условие

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

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

Тесты:

Код на Java:

Ход решения:

Ссылки: