e-olymp 13. Паук и муха

23/12/2018 by Саша Рябова

Задача

В пустой прямоугольной комнате размерами $A \times B \times C$ (длина, ширина, высота) на пол упала уснувшая муха. Паук, находившийся на одной из стен, или на полу комнаты, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится?

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

В первой строке заданы размеры комнаты $A$, $B$, $C$. Во второй строке — координаты мухи $X_1$,$Y_1$ и паука $X_2$, $Y_2$, $Z_2$.

Все входные данные — целые числа, не превышающие $500$.

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

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

Тесты

Входные данные	Выходные данные
$3$ $4$ $8$ $0$ $0$ $3$ $4$ $0$	$5.00$
$2$ $2$ $8$ $1$ $1$ $2$ $1$ $4$	$5.00$
$6$ $4$ $3$ $5$ $1$ $0$ $2$ $1$	$6.08$
$30$ $60$ $27$ $13$ $21$ $8$ $0$ $17$	$38.33$
$40$ $40$ $40$ $10$ $5$ $8$ $40$ $37$	$72.03$

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

import java.io.PrintStream;
import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static double distance (double X1,double X2,double Y1,double Y2)
    {
        return (Math.sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)));
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double A = sc.nextDouble();
        double B = sc.nextDouble();
        double C = sc.nextDouble();
        double X1 = sc.nextDouble();
        double Y1 = sc.nextDouble();
        double X2 = sc.nextDouble();
        double Y2 = sc.nextDouble();
        double Z2 = sc.nextDouble();
        double result_distance = Double.MAX_VALUE;
        if (Z2==0) result_distance = distance(X1,X2,Y1,Y2);//"floor" case
        else
        {
            if (X2==0) {
                X2=-Z2;
                result_distance = distance (X1,X2,Y1,Y2);
            }//"left wall" case
            if (X2==A) {
                X2=A+Z2;
                result_distance = distance (X1,X2,Y1,Y2);
            }//"right wall" case
            if (Y2==0) {
                Y2=-Z2;
                result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));
            }//"near wall" case
            if (Y2==B) {
                Y2=B+Z2;
                result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));
            }//"distant wall" case
        }
        System.out.printf("%.2f", result_distance);
    }
}

import java.io.PrintStream;

import java.util.Scanner;

import java.lang.Math;

public class Main {

public static double distance (double X1,double X2,double Y1,double Y2)

{

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

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

double A = sc.nextDouble();

double B = sc.nextDouble();

double C = sc.nextDouble();

double X1 = sc.nextDouble();

double Y1 = sc.nextDouble();

double X2 = sc.nextDouble();

double Y2 = sc.nextDouble();

double Z2 = sc.nextDouble();

double result_distance = Double.MAX_VALUE;

if (Z2==0) result_distance = distance(X1,X2,Y1,Y2);//"floor" case

else

{

if (X2==0) {

X2=-Z2;

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

}//"left wall" case

if (X2==A) {

X2=A+Z2;

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

}//"right wall" case

if (Y2==0) {

Y2=-Z2;

result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));

}//"near wall" case

if (Y2==B) {

Y2=B+Z2;

result_distance = Math.min(result_distance, distance (X1,X2,Y1,Y2));

}//"distant wall" case

}

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

}

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

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

Переведя координаты паука в комнате в его новые координаты в двумерном пространстве, все, что нам остается сделать — вычислить кратчайшее расстояние между двумя точками на плоскости с помощью функции $distance$.
В простейшем случае, если паук находится на полу комнаты, т.е. его координата $Z2$ нулевая, координаты паука $X2$ и $Y2$ в точности описывают его положение в координатной плоскости развёртки, и преобразовывать их не требуется.
В противном случае отдельно рассматриваем варианты расположения паука на каждой из стен. В зависимости от того, на какой стене он находится, мы изменяем координаты в соответствии с развёрткой комнаты и находим расстояние от паука до мухи с помощью функции $distance$.
В случае местонахождения паука в каком-либо из углов комнаты, но не на полу, мы должны рассмотреть два варианта его положения в развёртке и найти минимальное из них.

Ссылки

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

e-olymp 396. Дождь

18/12/2018 by Дима Мороз

Задача

Как это выглядит на координатной плоскости

Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X_0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $Y=0$.

Входные данные: во входном файле в первой строке содержатся два целых числа через пробел – координата $X_0$ точки появления капли $(0 < X_0 < 10000)$ и количество отрезков-препятствий $N(0≤N≤100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x_1, y_1, x_2, y_2$ – координаты левого и правого концов отрезка-препятствия $($все числа целые и находятся в диапазоне от $0$ до $10000, x_1 < x_2, y_1 ≠y_2)$. Отрезки не пересекаются и не соприкасаются.

Выходные данные: в выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные	Выходные данные
30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
12 5 12 9 13 5 17 8 19 5 13 10 10 7 6 17 4 12 13 4 5 12	13
40 3 12 30 21 39 41 5 45 70 20 30 25 35	40
70 6 45 75 598 37 489 48 726 47 673 873 46 36 60 735 373 762 483 73 364 59 462 375 583 457	726

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

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

class Main
{
	static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	static PrintWriter out = new PrintWriter(System.out);
	static int nextInt() throws IOException  {
		in.nextToken();
		return (int)in.nval;
	}
	public static void main (String[] args) throws java.lang.Exception
	{
    	int x = nextInt(), n = nextInt();
    	int N[][] = new int[n][4];;
    	int tmp = 0;
    	for (int i = 0; i < n; i++)
    	    for (int j = 0; j < 4; j++)
    	        N[i][j] = nextInt();
    	for (int i = 0; i < n; i++) 
    	    for (int j = 0; j < n; j++) 
    	        for (int q = 0; q < 4; q++)
    	            if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) ) {
    	                tmp = N[i][q];
    	                N[i][q] = N[j][q];
    	                N[j][q] = tmp;
    	            }
    	for (int i = 0; i < n; i++) {
    	    if (x >= N[i][0] && x <= N[i][2]) 
    	        x = (N[i][1] < N[i][3]) ? N[i][0] : N[i][2];
    	    for (int j = 0; j < 4; j++)
    	        N[i][j] = 0;
    	}
    	out.println(x);
    	out.flush();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

static PrintWriter out = new PrintWriter(System.out);

static int nextInt() throws IOException {

in.nextToken();

return (int)in.nval;

}

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

{

int x = nextInt(), n = nextInt();

int N[][] = new int[n][4];;

int tmp = 0;

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

for (int j = 0; j < 4; j++)

N[i][j] = nextInt();

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

for (int j = 0; j < n; j++)

for (int q = 0; q < 4; q++)

if ((N[i][1] > N[j][1] || N[i][3] > N[j][3]) || ( (N[i][1] == N[j][1] || N[i][3] == N[j][3] ) && (N[i][0] > N[j][0] || N[i][2] > N[j][2]) ) ) {

tmp = N[i][q];

N[i][q] = N[j][q];

N[j][q] = tmp;

}

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

if (x >= N[i][0] && x <= N[i][2])

x = (N[i][1] < N[i][3]) ? N[i][0] : N[i][2];

for (int j = 0; j < 4; j++)

N[i][j] = 0;

}

out.println(x);

out.flush();

}

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

Если $X\in[x_1,x_2]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
Тогда мы сравниваем координаты $y_1$ и $y_2$, выбираем из них наименьшее и присваиваем соответствующую координату $x_1$ или $x_2$ координате
нашей капли $X$.
Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

java@Cat

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

Tag Archives: система координат

e-olymp 13. Паук и муха

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 396. Дождь

Задача

Тесты

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

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

Ссылки