Рубрики

Максимально возможное пересечение движущимися центрами отрезков

Даны три точки на оси X, которые обозначают центр трех отрезков. Длина отрезка линии также задается как L. Задача состоит в том, чтобы переместить центр заданных отрезков на расстояние K, чтобы максимизировать длину пересечения между тремя линиями.

Примеры:

Input: c1 = 1, c2 = 2, c3 = 3, L = 1, K = 0
Output: 0
Since, no center can be moved, there is no intersection among three segments {(0.5, 1.5), (1.5, 2.5), (2.5, 3.5)}.

Input: c1 = 1, c2 = 2, c3 = 3, L = 1, K = 1
Output: 1
Center’s 1 and 3 can be shifted 1 unit ahead and forward respectively to overlap with center 2

Сегменты линии будут следующими:

  1. Линия-сегмент 1: (Center1-L / 2, Center1 + L / 2)
  2. Линия-сегмент 2: (Center2-L / 2, Center2 + L / 2)
  3. Линия-сегмент 3: (Center3-L / 2, Center3 + L / 2)

Подход: Изначально сортируйте центры, поскольку средний сегмент никогда не будет двигаться, так как левый и правый сегменты всегда могут приблизиться к своему центру, чтобы увеличить длину пересечения. Будет три случая, которые должны быть рассмотрены:

  • Случай 1: Когда расстояние между центрами справа и слева больше или равно 2 * K + L, в таком сценарии пересечение всегда будет нулевым. Наложение невозможно, поскольку даже после смещения обоих центров на расстояние K они будут удалены на расстоянии L или более.
  • Случай 2: Когда расстояние между центрами справа и слева больше или равно 2 * K, в таком сценарии существует пересечение, равное (2 * k — (center [2] — center [0] — length) )), который можно рассчитать, используя простую математику.
  • Случай 3: Когда расстояние между правым и левым центрами меньше 2 * К, в таком случае оба центра могут совпадать со средним центром. Следовательно, пересечение является L.

Ниже приведена реализация вышеуказанного подхода:

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати максимального пересечения

int max_intersection(int* center, int length, int k)

{

    sort(center, center + 3);

  

    // Дело 1

    if (center[2] - center[0] >= 2 * k + length) {

        return 0;

    }

  

    // Случай 2

    else if (center[2] - center[0] >= 2 * k) {

        return (2 * k - (center[2] - center[0] - length));

    }

  

    // Случай 3

    else

        return length;

}

  
// Код драйвера

int main()

{

    int center[3] = { 1, 2, 3 };

    int L = 1;

    int K = 1;

    cout << max_intersection(center, L, K);

}

Джава

// реализация Java
// вышеуказанного подхода

import java.util.*;

  

class GFG

{

  
// Функция для печати
// максимальное пересечение

static int max_intersection(int center[], 

                            int length, int k) 

    Arrays.sort(center); 

  

    // Дело 1

    if (center[2] - center[0] >= 2 * k + length) 

    

        return 0

    

  

    // Случай 2

    else if (center[2] - center[0] >= 2 * k)

    

        return (2 * k - (center[2] - 

                center[0] - length)); 

    

  

    // Случай 3

    else

        return length; 

  
// Код драйвера

public static void main(String args[])

    int center[] = { 1, 2, 3 }; 

    int L = 1

    int K = 1

    System.out.println( max_intersection(center, L, K)); 


}

  
// Этот код добавлен
// Арнаб Кунду

python3

# Python3 реализация вышеуказанного подхода

  
# Функция для печати максимального пересечения

def max_intersection(center, length, k): 

  

    center.sort(); 

  

    # Дело 1

    if (center[2] - center[0] >= 2 * k + length):

        return 0

  

    # Случай 2

    elif (center[2] - center[0] >= 2 * k):

        return (2 * k - (center[2] - center[0] - length)); 

  

    # Дело 3

    else:

        return length; 

  
Код водителя

center = [1, 2, 3]; 

L = 1

K = 1

print(max_intersection(center, L, K)); 

  
# Этот код добавлен
# по митсам

C #

// реализация C #
// вышеуказанного подхода

using System;

  

class GFG

{

  
// Функция для печати
// максимальное пересечение

static int max_intersection(int []center, 

                            int length, int k) 

    Array.Sort(center); 

  

    // Дело 1

    if (center[2] - center[0] >= 2 * k + length) 

    

        return 0; 

    

  

    // Случай 2

    else if (center[2] - 

             center[0] >= 2 * k)

    

        return (2 * k - (center[2] - 

                         center[0] - length)); 

    

  

    // Случай 3

    else

        return length; 

  
// Код драйвера

public static void Main()

    int []center = { 1, 2, 3 }; 

    int L = 1; 

    int K = 1; 

    Console.WriteLine(max_intersection(center, L, K)); 


}

  
// Этот код добавлен
// Субхадип Гупта

PHP

<?php
// реализация PHP
// вышеуказанного подхода

  
// Функция для печати
// максимальное пересечение

function max_intersection($center

                          $length, $k

    sort($center); 

  

    // Дело 1

    if ($center[2] - 

        $center[0] >= 2 * $k + $length

    

        return 0; 

    

  

    // Случай 2

    else if ($center[2] - 

             $center[0] >= 2 * $k)

    

        return (2 * $k - ($center[2] - 

             $center[0] - $length)); 

    

  

    // Случай 3

    else

        return $length

  
// Код драйвера

$center = array(1, 2, 3); 

$L = 1; 

$K = 1; 

echo max_intersection($center, $L, $K); 

  
// Этот код добавлен
// по миц
?>

Выход:

1

Рекомендуемые посты:

Максимально возможное пересечение движущимися центрами отрезков

0.00 (0%) 0 votes