e-olymp 9081. Автомобілі

10/09/2020 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$, $v_2$, $v_3$, $t_1$, $t_2$, $t_3$. Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

public class Main {

    public static void main(String[] args) {
        java.util.Scanner jin = new java.util.Scanner(System.in);
            int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
            int t1, t2, t3; // Час, який вони їхали
            int s1, s2, s3; // І відстань
            int max_; // Також, змінну, де буде зберігатися максимальна відстань
            v1 = jin.nextInt(); t1 = jin.nextInt(); // Прочитуємо швидкість і час для кожного водія
            v2 = jin.nextInt(); t2 = jin.nextInt();
            v3 = jin.nextInt(); t3 = jin.nextInt();
            s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
            s2 = v2 * t2;
            s3 = v3 * t3;
            max_ = Math.max(Math.max(s1, s2), s3); // Виявляємо максимальну відстань
            if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
                System.out.print("1 "); // Виводимо номер відповідного водія
            if ( s2 == max_ )
                System.out.print("2 ");
            if ( s3 == max_ )
                System.out.print(3);
            
        }
}

public class Main {

public static void main(String[] args) {

java.util.Scanner jin = new java.util.Scanner(System.in);

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

v1 = jin.nextInt(); t1 = jin.nextInt(); // Прочитуємо швидкість і час для кожного водія

v2 = jin.nextInt(); t2 = jin.nextInt();

v3 = jin.nextInt(); t3 = jin.nextInt();

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = Math.max(Math.max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

System.out.print("1 "); // Виводимо номер відповідного водія

if ( s2 == max_ )

System.out.print("2 ");

if ( s3 == max_ )

System.out.print(3);

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$. Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.

Посилання

e-olymp 74. Паук и муха — 2

01/12/2018 by Алиса Ворохта

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

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

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

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

Одно число – расстояние, на которое переместится паук, посчитанное с точностью до 2-х знаков после запятой.

Тесты

Входные данные								Выходные данные
[latex]A[/latex]	[latex]B[/latex]	[latex]C[/latex]	[latex]X1[/latex]	[latex]Y1[/latex]	[latex]X2[/latex]	[latex]Y2[/latex]	[latex]Z2[/latex]	[latex]S[/latex]
[latex]4[/latex]	[latex]7[/latex]	[latex]3[/latex]	[latex]2[/latex]	[latex]1[/latex]	[latex]3[/latex]	[latex]7[/latex]	[latex]2[/latex]	[latex]8.06[/latex]
[latex]145[/latex]	[latex]26[/latex]	[latex]306[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]0[/latex]	[latex]305[/latex]	[latex]309.34[/latex]
[latex]26[/latex]	[latex]18[/latex]	[latex]53[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]24[/latex]	[latex]1[/latex]	[latex]53[/latex]	[latex]58.52[/latex]
[latex]89[/latex]	[latex]89[/latex]	[latex]189[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]89[/latex]	[latex]16[/latex]	[latex]70.77[/latex]
[latex]18[/latex]	[latex]26[/latex]	[latex]145[/latex]	[latex]14[/latex]	[latex]2[/latex]	[latex]17[/latex]	[latex]26[/latex]	[latex]141[/latex]	[latex]147.14[/latex]

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

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

class Main
{
	private static double distance(long X1, long Y1, long X2, long Y2) 
	{
    	return Math.sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		long A = in.nextLong();
		long B = in.nextLong();
		long C = in.nextLong();
		long X1 = in.nextLong();
		long Y1 = in.nextLong();
		long X2 = in.nextLong();
		long Y2 = in.nextLong();
		long Z2 = in.nextLong();
		double S = 10000000;
		if (Z2 == 0)
    	{
    		S = distance(X1, Y1, X2, Y2);
    	}
		else
		{
			if (X2 == 0)
			{
				S = Math.min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));
				S = Math.min(S, distance(X1, Y1, Y2 - B, B + Z2));
			}
			if (X2 == A)
			{
				S = Math.min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));
				S = Math.min(S, distance(X1, Y1, A + B - Y2, Z2 + B));
			}
			if (Y2 == 0)
			{
				S = Math.min(S, distance(X1, Y1, X2, -Z2));
				S = Math.min(S, distance(X1, Y1, -Z2, -X2));
				S = Math.min(S, distance(X1, Y1, A + Z2, X2 - A));
			}
			if (Y2 == B)
			{
				S = Math.min(S, distance(X1, Y1, X2, Z2 + B));
				S = Math.min(S, distance(X1, Y1, -Z2, X2 + B));
				S = Math.min(S, distance(X1, Y1, A + Z2, B + A - X2));
			}
			if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))
			{
				S = Math.min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));
				S = Math.min(S, distance(X1, Y1, X2, 2*B - Y2 + C));
				S = Math.min(S, distance(X1, Y1, -X2 - C, Y2));
				S = Math.min(S, distance(X1, Y1, 2*A - X2 + C, Y2));
				S = Math.min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));
				S = Math.min(S, distance(X1, Y1, A + C + Y2, X2 - A));
				S = Math.min(S, distance(X1, Y1, -C - Y2, -X2));
				S = Math.min(S, distance(X1, Y1, Y2 - B - C, B + X2));
				S = Math.min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));
				S = Math.min(S, distance(X1, Y1, Y2 - B, B + C + X2));
				S = Math.min(S, distance(X1, Y1, -Y2, -C - X2));
				S = Math.min(S, distance(X1, Y1, A + Y2, -A - C + X2));
			}
		}
		System.out.printf("%.2f", S);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

private static double distance(long X1, long Y1, long X2, long Y2)

{

return Math.sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));

}

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

{

Scanner in = new Scanner(System.in);

long A = in.nextLong();

long B = in.nextLong();

long C = in.nextLong();

long X1 = in.nextLong();

long Y1 = in.nextLong();

long X2 = in.nextLong();

long Y2 = in.nextLong();

long Z2 = in.nextLong();

double S = 10000000;

if (Z2 == 0)

{

S = distance(X1, Y1, X2, Y2);

}

else

{

if (X2 == 0)

{

S = Math.min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));

S = Math.min(S, distance(X1, Y1, Y2 - B, B + Z2));

}

if (X2 == A)

{

S = Math.min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));

S = Math.min(S, distance(X1, Y1, A + B - Y2, Z2 + B));

}

if (Y2 == 0)

{

S = Math.min(S, distance(X1, Y1, X2, -Z2));

S = Math.min(S, distance(X1, Y1, -Z2, -X2));

S = Math.min(S, distance(X1, Y1, A + Z2, X2 - A));

}

if (Y2 == B)

{

S = Math.min(S, distance(X1, Y1, X2, Z2 + B));

S = Math.min(S, distance(X1, Y1, -Z2, X2 + B));

S = Math.min(S, distance(X1, Y1, A + Z2, B + A - X2));

}

if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))

{

S = Math.min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));

S = Math.min(S, distance(X1, Y1, X2, 2*B - Y2 + C));

S = Math.min(S, distance(X1, Y1, -X2 - C, Y2));

S = Math.min(S, distance(X1, Y1, 2*A - X2 + C, Y2));

S = Math.min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));

S = Math.min(S, distance(X1, Y1, A + C + Y2, X2 - A));

S = Math.min(S, distance(X1, Y1, -C - Y2, -X2));

S = Math.min(S, distance(X1, Y1, Y2 - B - C, B + X2));

S = Math.min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));

S = Math.min(S, distance(X1, Y1, Y2 - B, B + C + X2));

S = Math.min(S, distance(X1, Y1, -Y2, -C - X2));

S = Math.min(S, distance(X1, Y1, A + Y2, -A - C + X2));

}

System.out.printf("%.2f", S);

}

Решение задачи

Данная задача решается с помощью «разверток» комнаты: переход от трёхмерного пространства к двумерному.
Вид комнаты:

Рассмотрим такие случаи:

Паук находится на полу ([latex]Z_2 = 0[/latex]);
Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

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

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

Паук спускается с потолка на паутине, затем ползет точно так же, как и в самом первом случае.
Паук ползет по потолку, по одной из стенок и по полу. Тогда развертка будет выглядеть следующим образом (потолок можно развернуть в 4 стороны — отсюда 4 случая):
Паук ползет по потолку, а затем по двум соседним стенкам и по полу. Таких случаев 8, поскольку порядок следования стенок, по которым тот ползет, также важен. Развертка одного из них:

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи.

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

e-olymp 49. Кот учёный

19/11/2018 by Костя Григорян

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

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

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

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

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

Тесты

Входные данные	Выходные данные
[latex]4\, 4\, 2[/latex]	[latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex]	[latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex]	[latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

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

import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int l = scanner.nextInt();
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int count = 0;
		for(int i=0; i<n; i++) {
			int x1 = scanner.nextInt();
			int y1 = scanner.nextInt();
			int x2 = scanner.nextInt();
			int y2 = scanner.nextInt();
			if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)
				count++;
			else {
			 	int a, b, c;
		    	int deltaX=x2-x1;
				int deltaY=y2-y1;
		    	a=deltaY;
		    	b=-deltaX;
		    	c=y1*deltaX-x1*deltaY;
		    	if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*Math.max(y2, y1)&&-c*b>=(b*b+a*a)*Math.min(y2, y1)))
		        	count++;
			}
		}
		System.out.println(count/k+1);
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int l = scanner.nextInt();

int n = scanner.nextInt();

int k = scanner.nextInt();

int count = 0;

for(int i=0; i<n; i++) {

int x1 = scanner.nextInt();

int y1 = scanner.nextInt();

int x2 = scanner.nextInt();

int y2 = scanner.nextInt();

if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)

count++;

else {

int a, b, c;

int deltaX=x2-x1;

int deltaY=y2-y1;

a=deltaY;

b=-deltaX;

c=y1*deltaX-x1*deltaY;

if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*Math.max(y2, y1)&&-c*b>=(b*b+a*a)*Math.min(y2, y1)))

count++;

}

System.out.println(count/k+1);

}

Решение задачи

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

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

ML36. Движение катера

28/06/2017 by Черноглазов Николай

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

Катер движется по течению реки из пункта A в пункт B и обратно с собственной скоростью $latex v$ км/час. Скорость течения постоянна — $latex u$ км/час. Расстояние между пунктами составляет $latex s$ км. Для любых действительных неотрицательных значений расстояния и скоростей вычислить время в пути $latex t_{boat}$.

Тесты

Входные данные: физические величины $latex v$, $latex u$, $latex s$

Выходные данные: физическая величина $latex t_{boat}$

№	Входные данные	Выходные данные
1	3 2 10	12.0
2	1.4 0.4 3.6	5.6
3	3 6 10	Infinity
4	2 1 0	0.0

Код

import java.util.Scanner;

class ML36
{
	public static void main (String[] args)
	{
		double v, u, s, t;
		double inf = Double.POSITIVE_INFINITY;
		Scanner scanner = new Scanner(System.in);
		
		v = scanner.nextDouble();
		u = scanner.nextDouble();
		s = scanner.nextDouble();
		
		t = (v>=u) ? s/(v+u) + s/(v-u) : inf;
		
		System.out.println(t);
	}
}

import java.util.Scanner;

class ML36

{

public static void main (String[] args)

{

double v, u, s, t;

double inf = Double.POSITIVE_INFINITY;

Scanner scanner = new Scanner(System.in);

v = scanner.nextDouble();

u = scanner.nextDouble();

s = scanner.nextDouble();

t = (v>=u) ? s/(v+u) + s/(v-u) : inf;

System.out.println(t);

}

Код доступен на ideone

Пояснение

Скорость катера, когда он идет по течению, равна $latex (v+u)$, а когда против — $latex (v-u)$. Время $latex t$ вычисляется по формуле $latex t = \frac{s}{v}\\ $, где $latex s$ — расстояние, $latex v$ — скорость, соответственно общее время пути катера составит $latex t_{boat} = {\frac{s}{v+u}\\+\frac{s}{v-u}\\} $. При этом время — величина неотрицательная, а делитель дроби не должен быть нулевым, соответственно имеем ограничение $latex v-u > 0, v > u $.

java@Cat

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

Tag Archives: расстояние

e-olymp 9081. Автомобілі

Завдання

Вхідні дані

Вихідні дані

Тести

Код програми

Пояснення

Посилання

e-olymp 74. Паук и муха — 2

Задача

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

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

Тесты

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

Решение задачи

Ссылки

e-olymp 49. Кот учёный

Задача

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

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

Тесты

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

Решение задачи

Ссылки

ML36. Движение катера