E079. Точка пересечения прямых

e-maxx algorithm original: C/C++ #algorithm #emaxx #geometry #math
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Static

Источник: e-maxx.ru/algo, страница PDF 232.

Пусть нам given две прямые, заданные своими коэффициентами

и

. it is required find их

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

Solución

Если две прямые не параллельны, то они пересекаются. Чтобы find точку пересечения, достаточно составить из двух уравнений прямых систему и решить её: Пользуясь формулой Крамера, сразу находим Solución системы, которое и будет искомой точкой пересечения:

Если знаменатель нулевой, т.е. то система решений не имеет (прямые параллельны и не совпадают) или имеет бесконечно много (прямые совпадают). Если необходимо различить эти два случая, надо проверить, что коэффициенты

прямых пропорциональны с тем же коэффициентом пропорциональности, что и коэффициенты

и

, для

чего достаточно посчитать два определителя, если они оба равны нулю, то прямые совпадают:

Implementación

struct pt {

double x, y;

};

struct line {

double a, b, c;

};

const double EPS = 1e-9;

double det (double a, double b, double c, double d) {

return a * d - b * c;

}

bool intersect (line m, line n, pt & res) {

double zn = det (m.a, m.b, n.a, n.b);

if (abs (zn) < EPS)
return false;

res.x = - det (m.c, m.b, n.c, n.b) / zn;

res.y = - det (m.a, m.c, n.a, n.c) / zn;

return true;

}

bool parallel (line m, line n) {

return abs (det (m.a, m.b, n.a, n.b)) < EPS;

}

bool equivalent (line m, line n) {

return abs (det (m.a, m.b, n.a, n.b)) < EPS

&& abs (det (m.a, m.c, n.a, n.c)) < EPS

&& abs (det (m.b, m.c, n.b, n.c)) < EPS;

}

C# solución

borrador automático, revisar antes de enviar 
using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            double x, y;
    };
    struct line {
            double a, b, c;
    };
    const double EPS = 1e-9;
    double det (double a, double b, double c, double d) {
            return a * d - b * c;
    }
    bool intersect (line m, line n, pt & res) {
            double zn = det (m.a, m.b, n.a, n.b);
            if (abs (zn) < EPS)
                    return false;
            res.x = - det (m.c, m.b, n.c, n.b) / zn;
            res.y = - det (m.a, m.c, n.a, n.c) / zn;
            return true;
    }
    bool parallel (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS;
    }
    bool equivalent (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS
                    && abs (det (m.a, m.c, n.a, n.c)) < EPS
                    && abs (det (m.b, m.c, n.b, n.c)) < EPS;
    }
}

C++ solución

coincidente/original 
struct pt {
        double x, y;
};
struct line {
        double a, b, c;
};
const double EPS = 1e-9;
double det (double a, double b, double c, double d) {
        return a * d - b * c;
}
bool intersect (line m, line n, pt & res) {
        double zn = det (m.a, m.b, n.a, n.b);
        if (abs (zn) < EPS)
                return false;
        res.x = - det (m.c, m.b, n.c, n.b) / zn;
        res.y = - det (m.a, m.c, n.a, n.c) / zn;
        return true;
}
bool parallel (line m, line n) {
        return abs (det (m.a, m.b, n.a, n.b)) < EPS;
}
bool equivalent (line m, line n) {
        return abs (det (m.a, m.b, n.a, n.b)) < EPS
                && abs (det (m.a, m.c, n.a, n.c)) < EPS
                && abs (det (m.b, m.c, n.b, n.c)) < EPS;
}

Java solución

borrador automático, revisar antes de enviar 
import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            double x, y;
    };
    struct line {
            double a, b, c;
    };
    const double EPS = 1e-9;
    double det (double a, double b, double c, double d) {
            return a * d - b * c;
    }
    boolean intersect (line m, line n, pt & res) {
            double zn = det (m.a, m.b, n.a, n.b);
            if (abs (zn) < EPS)
                    return false;
            res.x = - det (m.c, m.b, n.c, n.b) / zn;
            res.y = - det (m.a, m.c, n.a, n.c) / zn;
            return true;
    }
    boolean parallel (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS;
    }
    boolean equivalent (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS
                    && abs (det (m.a, m.c, n.a, n.c)) < EPS
                    && abs (det (m.b, m.c, n.b, n.c)) < EPS;
    }
}

Материал разбит как Algoritmoическая Tarea: изучить постановку, понять асимптотику и реализовать Algoritmo на выбранном языке.

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.