Из заданного набора прямых линий, как найти точки, лежащие на любой линии, имеющие минимальную координату y в конкретном x?

Question

Наивным решением было бы выполнить итерацию по каждому уравнению прямой (из них ~ 1e5), заменить x на заданное значение, получить y и сравнить это y с y, полученным издругие уравнения прямой.Однако это решение не может быть выполнено в течение установленного срока, если количество запросов велико (~ 1e5).Есть ли эффективный способ найти минимальное «у» для конкретного «х»?

Код JAVA, который не удается:

import java.util.Scanner;

class Competitive_Programming
{
    static Scanner sc = new Scanner(System.in);
    static int N, M;
    static StLine[] lines;

    public static void main(String[] args)
    {
        int i, j;

        N = sc.nextInt();   // Number of straight lines (~1e5)
        lines = new StLine[N];
        for(i = 0; i < N; ++i)
        {
            double m = sc.nextDouble(); // slope
            double c = sc.nextDouble(); //y-intercept
            lines[i] = new StLine(m, c);
        }

        M = sc.nextInt();   // Number of queries (~1e5)
        for(i = 0; i < M; ++i)
        {
            double x = sc.nextDouble(); // The X co-ordinate
            double minY = Double.MAX_VALUE;
            for(j = 0; j < N; ++j)
                minY = Math.min(minY, lines[j].YatX(x));
            System.out.println(minY);   // Minimum Y co-ordinate
        }
    }
}
class StLine
{
    double slope, yintercept;
    StLine(double m, double c)
    {
        slope = m;  yintercept = c;
    }
    double YatX(double x)
    {
        return x * slope + yintercept;
    }
}

Answer 1

Локус наименьшего y для любого x является выпуклой ломаной с не более чем N-1 вершинами.

Вы можете построить его постепенно, добавляя по одной строке за раз.Обновление ломаной линии не очень сложно, если все сделано наивным способом: для каждого сегмента проверьте, пересекает ли он новую линию, и оставьте только части «ниже».Обязательно сохраняйте порядок вершин слева направо.

Я подозреваю, что эта операция может выполняться более эффективно с помощью дихотомических процессов, но для этого требуются более сложные структуры данных.

Когда вы получили окончательную полилинию, требуется простой дихотомический поиск, чтобы найти y для данного x.