вычислительная геометрия

Задача из журнала «Квант» №4 1970г.

Крестьянин, подойдя к развилке двух дорог, расходящихся под углом 60°, спросил: <Как пройти в село [latex]NN?[/latex]> Ему ответили: <Иди по левой дороге до деревни [latex]N[/latex] — это в восьми верстах отсюда,— там увидишь, что направо под прямым углом отходит большая ровная дорога,— это как раз дорога в [latex]NN[/latex]. А можешь идти другим путём: сейчас по правой дороге; как выйдешь к железной дороге,— значит, половину пути прошёл; тут поверни налево и иди прямо по шпалам до самого NN>. — <Ну, а какой путь короче-то будет?> — <Да всё равно, что так, что этак, никакой разницы.> И пошёл крестьянин по правой дороге. Сколько вёрст ему придётся идти до NN? Больше десяти или меньше? А если идти от развилки до [latex]NN[/latex] напрямик? (Все дороги прямые.)

Более лаконичная версия:
Крестьянин стоит на развилке дорог, которые расходятся под углом 60°, и хочет попасть в село [latex]NN[/latex]. Выбрав левую дорогу, он должен будет пройти [latex]n[/latex] вёрст прямо, затем повернуть направо под прямым углом и идти до [latex]NN[/latex]. Выбрав правую, он должен будет преодолеть участок некоторой длины прямо, затем повернуть налево и пройти такой же по длине участок. При этом известно, что длины левой и правой дорог одинаковы. От нас требуется найти длину пути по одной из дорог и длину пути напрямик.

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

Длина пути от развилки до N.

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

Длины путей по дороге и напрямик.

Тесты.

№	Входные данные	Выходные данные
	[latex]n[/latex]	[latex]{ s }_{ 1 }[/latex]	[latex]{ s }_{ 2 }[/latex]
1	0	0	0
2	8	11.0416	8.55871
3	0.5	0.690101	0.534919
4	21	28.9843	22.4666
5	13.45	18.5637	14.3893

Код программы (C++).

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double s1, s2, n, x;
    cin >> n;
    x = n*(5-sqrt(3)-sqrt(6*sqrt(3)-4))/(8*(2-sqrt(3)));
    s1 = 4*x; //Длина пути по дороге
    s2 = sqrt(2*(n*n - 4*x*n + 8*x*x)); //Длина пути напрямик
    cout << s1 <<' ' << s2;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double s1, s2, n, x;

cin >> n;

x = n*(5-sqrt(3)-sqrt(6*sqrt(3)-4))/(8*(2-sqrt(3)));

s1 = 4*x; //Длина пути по дороге

s2 = sqrt(2*(n*n - 4*x*n + 8*x*x)); //Длина пути напрямик

cout << s1 <<' ' << s2;

return 0;

}

Код программы (Java).

import java.util.*;
import java.math.*;

class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        double s1, s2, n, x;
        n = in.nextDouble();
        x = n*(5-Math.sqrt(3)-Math.sqrt(6*Math.sqrt(3)-4))/(8*(2-Math.sqrt(3)));
        s1 = 4*x; //Длина пути по дороге
        s2 = Math.sqrt(2*(n*n - 4*x*n + 8*x*x)); //Длина пути напрямик
        System.out.print(s1 + " " + s2);
    }
}

import java.util.*;

import java.math.*;

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double s1, s2, n, x;

n = in.nextDouble();

x = n*(5-Math.sqrt(3)-Math.sqrt(6*Math.sqrt(3)-4))/(8*(2-Math.sqrt(3)));

s1 = 4*x; //Длина пути по дороге

s2 = Math.sqrt(2*(n*n - 4*x*n + 8*x*x)); //Длина пути напрямик

System.out.print(s1 + " " + s2);

}

Решение.
Обозначим развилку как [latex]A[/latex], деревню [latex]N[/latex] как [latex]B[/latex], село [latex]NN[/latex] как [latex]C[/latex], место пересечения правой дороги с рельсами как D, и проведём [latex]DH\bot AB[/latex] и [latex]DK\bot BC[/latex]. Нам дано, что [latex]AB=n[/latex], угол [latex]BAC[/latex] — 60 градусов, [latex]AD=DC[/latex] и [latex]AB+BC=AD+CD[/latex].

Пусть [latex]AD=2x[/latex], тогда [latex]AH=x[/latex]; [latex]BH=KD=n-x[/latex]; [latex]BC=4x-n[/latex]; Из треугольника [latex]AHD[/latex]: [latex]BK=DH=x\cdot \sqrt { 3 } [/latex];

[latex]KC=KB-BC=n+x\cdot (\sqrt { 3 } -4)[/latex].
Из треугольника CKD по теореме Пифагора: [latex]{ KC }^{ 2 }+{ KD }^{ 2 }={ CD }^{ 2 }[/latex]. Подставив значения, раскрыв скобки и проведя математические преобразования, получим квадратное уравнение [latex]{ x }^{ 2 }\cdot (-4\sqrt { 3 } +8)-x\cdot n\cdot (\sqrt { 3 } -5)+{ n }^{ 2 }=0[/latex].
Найдём дискриминант [latex]D={ n }^{ 2 }\cdot (6\sqrt { 3 } -4)[/latex].

[latex]KD=n-x[/latex] и [latex]KD>0[/latex], значит, [latex]n-x>0[/latex] и [latex]x<n[/latex]. Легко доказать, что для первого из корней полученного квадратного уравнения это условие не выполняется. Значит, мы имеем лишь один корень. Найдя его, мы найдём половину длины [latex]AD[/latex]. Выведем формулу для его расчёта:
[latex]x=\frac { n\cdot (5-\sqrt { 3 } -\sqrt { 6\sqrt { 3 } -4 } ) }{ 8\cdot (2-\sqrt { 3 } ) } [/latex] Тогда длина пути по дороге будет равна [latex]4x[/latex], а длину пути напрямик мы найдём из треугольника [latex]ABC[/latex] по теореме Пифагора: [latex]{ s }_{ 2 }=\sqrt { { 2\cdot (n }^{ 2 }-4x\cdot n+8{ n }^{ 2 }) } [/latex].

Код на ideone.com: здесь (C++) и здесь (Java).
Условие задачи (страница 27).

Related Images:

Задача.

Треугольник и точка. Лежит ли точка [latex] M \left( x_{m}, y_{m} \right) [/latex] внутри треугольника, заданного координатами своих вершин [latex] \left( x_{A}, y_{A} \right) [/latex], [latex] \left( x_{A}, y_{A} \right) [/latex], [latex] \left( x_{A}, y_{A} \right) [/latex].

Комментарий.

Предполагаем, что треугольник невырожденный, т.е. точки [latex] A [/latex], [latex] B [/latex] и [latex] C [/latex] не лежат на одной прямой.

Слово «внутри» будем понимать следующим образом: точка «лежит внутри треугольника», если она принадлежит внутренности (в топологическом смысле) этого треугольника. Как следствие, если точка лежит на одной из сторон треугольника, внутри треугольника она НЕ лежит.

Тесты.

Ввод	Вывод
0 0 1 0 1 1 0.5 0.25	Да
0 0 1 0 1 1 -1 -1.5	Нет
-1.5 -1.5 -1.5 4 1 0.5 -1 2	Да
-1.5 -1.5 -1.5 4 1 0.5 -1 0	Нет
0.3 0.2 1.3 0.2 0.3 0.8 0.7 0.4	Да
0.3 0.2 1.3 0.2 0.3 0.8 0.3 0.6	Нет
2 1 0.5 -2 -2 -0.5 0.5 -1	Да
2 1 0.5 -2 -2 -0.5 2 1	Нет

Рассмотрим четыре основных типа треугольников:

ровно одна сторона параллельна оси абсцисс;
ровно одна сторона параллельна оси ординат;
две стороны параллельны координатным осям;
ни одна из сторон не параллельна ни к одной из осей.

Для каждого типа рассмотрим два случая: точка принадлежит его внутренности и не принадлежит. При этом рассмотрим случай (восьмая строка таблицы), когда точка лежит на стороне и постараемся рассмотреть случаи, когда координатами являются нецелые и отрицательные числа.

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

Код.

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int i;
	double a1, a2, b1, b2, c1, c2, x, y, f, g;
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a1, &a2, &b1, &b2, &c1, &c2, &x, &y);
	f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);
	g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);
	if (f*g > 0) {  // Проверяем, лежат ли точки (x,y) и C по одну сторону от прямой  AB 
		f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);
		g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);
		if (f*g > 0) {  // Проверяем, лежат ли точки (x,y) и B по одну сторону от прямой  AC 
			f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);
			g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);
			if (f*g > 0) {  // Проверяем, лежат ли точки (x,y) и A по одну сторону от прямой  BC 
				printf("Да \n");
			}
			else {
				printf("Нет \n");
			}
		}
		else {
			printf("Нет \n");
		}
	}
	else {
		printf("Нет \n");
	}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int i;

double a1, a2, b1, b2, c1, c2, x, y, f, g;

scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a1, &a2, &b1, &b2, &c1, &c2, &x, &y);

f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);

g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);

if (f*g > 0) { // Проверяем, лежат ли точки (x,y) и C по одну сторону от прямой AB

f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);

g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);

if (f*g > 0) { // Проверяем, лежат ли точки (x,y) и B по одну сторону от прямой AC

f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);

g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);

if (f*g > 0) { // Проверяем, лежат ли точки (x,y) и A по одну сторону от прямой BC

printf("Да \n");

}

else {

printf("Нет \n");

}

else {

printf("Нет \n");

}

else {

printf("Нет \n");

}

return 0;

}

Ideone (C++)

Код (Java)

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double a1 = in. nextDouble(), a2 = in. nextDouble();
		double b1 = in. nextDouble(), b2 = in. nextDouble();
		double c1 = in. nextDouble(),c2 = in. nextDouble();
		double x = in. nextDouble(), y = in. nextDouble(), f, g;
		f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);
		g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);
		if (f*g > 0) {
			f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);
			g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);
			if (f*g > 0) {
				f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);
				g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);
				if (f*g > 0)
					System.out.println("Yes\n");
				else
					System.out.println("No\n");
			}
			else
				System.out.println("No\n");
		}
		else
			System.out.println("No\n");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

double a1 = in. nextDouble(), a2 = in. nextDouble();

double b1 = in. nextDouble(), b2 = in. nextDouble();

double c1 = in. nextDouble(),c2 = in. nextDouble();

double x = in. nextDouble(), y = in. nextDouble(), f, g;

f = (y - a2)*(b1 - a1) - (x - a1)*(b2 - a2);

g = (c2 - a2)*(b1 - a1) - (c1 - a1)*(b2 - a2);

if (f*g > 0) {

f = (y - a2)*(c1 - a1) - (x - a1)*(c2 - a2);

g = (b2 - a2)*(c1 - a1) - (b1 - a1)*(c2 - a2);

if (f*g > 0) {

f = (y - b2)*(c1 - b1) - (x - b1)*(c2 - b2);

g = (a2 - b2)*(c1 - b1) - (a1 - b1)*(c2 - b2);

if (f*g > 0)

System.out.println("Yes\n");

else

System.out.println("No\n");

}

else

System.out.println("No\n");

}

else

System.out.println("No\n");

}

Ideone (Java)

Решение.

Составим уравнения сторон треугольника. Как известно, в эвклидовой геометрии в прямоугольных декартовых координатах уравнение прямой, проходящей через две (различные!) точки [latex] \left( r1, r2 \right) [/latex] и [latex] \left( s1, s2 \right) [/latex] есть [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) = 0[/latex] . Эта прямая разбивает плоскость на три части: собственно прямую и две открытые полуплоскости, задаваемые неравенствами [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) < 0[/latex] и [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right) > 0[/latex].
Как известно, точка лежит внутри невырожденного треугольника, если и только если она лежит с каждой вершиной этого треугольника в одной полуплоскости относительно стороны, противоположной этой вершине.
Из 1. заключаем, что точки с декартовыми координатами [latex] \left( x,y \right)[/latex] и [latex] \left( u,v \right)[/latex] лежат по одну сторону от прямой, проходящей через точки [latex] \left( r1,r2 \right)[/latex] и [latex] \left( s1,s2 \right)[/latex], если и только если числа [latex] \left(y — r2 \right) \left( s1 — r1 \right) — \left( x — r1 \right) \left( s2 — r2 \right)[/latex] и [latex] \left(v — r2 \right) \left( s1 — r1 \right) — \left( u- r1 \right) \left( s2 — r2 \right)[/latex] отличны от нуля и одного знака, т.е. если произведение этих чисел — строго положительное число.
Проверяем условие из пункта 3. для вершины [latex] C [/latex] и стороны [latex] AB [/latex]. Если условие выполнено, переходим к пункту 5. В противном случае точка внутри треугольника не лежит.
Проверяем условие из пункта 3. для вершины [latex] B [/latex] и стороны [latex] AC [/latex]. Если условие выполнено, переходим к пункту 5. В противном случае точка внутри треугольника не лежит.
Проверяем условие из пункта 3. для вершины [latex] A [/latex] и стороны [latex] BC [/latex]. Если условие выполнено, точка лежит внутри треугольника. В противном случае точка внутри треугольника не лежит.