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

e-maxx algorithm original: C/C++ #algorithm #emaxx #geometry #math

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

Static

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

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

и

. it is required find их

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

Lời giải

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

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

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

и

, для

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

Cài đặt

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# lời giải

bản nháp tự động, xem lại trước khi gửi

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++ lời giải

đã khớp/gốc

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 lời giải

bản nháp tự động, xem lại trước khi gửi

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;
    }
}

Материал разбит как Thuật toánическая Bài toán: изучить постановку, понять асимптотику и реализовать Thuật toán на выбранном языке.

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.