通过移动线段中心实现的最大可能交点-yiteyi-C++库

给定X轴上的三个点，表示三条线段的中心。线段的长度也表示为L。任务是将给定线段的中心移动K距离，以最大化三条线之间的相交长度。 例如：

null

输入： c1=1，c2=2，c3=3，L=1，K=0 输出： 0 因为没有中心可以移动，所以三段{（0.5,1.5）、（1.5,2.5）、（2.5,3.5）}之间没有交点。 输入： c1=1，c2=2，c3=3，L=1，K=1 输出： 1. 中锋1号和中锋3号可以分别向前和向前移动1个单位，与中锋2号重叠

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

线段如下所示：

线段1：（中心1-L/2，中心1+L/2）
线段2：（中心2-L/2，中心2+L/2）
线段3：（中心3-L/2，中心3+L/2）

方法： 首先对中心进行排序，因为中间段永远不会移动，因为左右段始终可以到达其中心附近，以增加相交长度。将处理三个案件：

案例1： 在这种情况下，当左右中心之间的距离大于或等于2*K+L时，交叉口将始终为零。不可能有重叠，因为即使在移动两个中心时仍然保持K距离，它们仍将保持L或更大的距离。
案例2： 在这种情况下，当左右中心之间的距离大于或等于2*K时，存在一个等于 （2*k–（中心[2]–中心[0]–长度）） 这可以用简单的数学计算出来。
案例3： 当左右中心之间的距离小于2*K时，在这种情况下，两个中心可以与中间中心重合。因此，交叉点为L。

以下是上述方法的实施情况：

C++

                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to print the maximum intersection                       
                         int                                     max_intersection(                                     int                                     * center,                                     int                                     length,                                     int                                     k)                       
                         {                       
                                                 sort(center, center + 3);                       
           
                                                 // Case 1                       
                                                 if                                     (center[2] - center[0] >= 2 * k + length) {                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // Case 2                       
                                                 else                                     if                                     (center[2] - center[0] >= 2 * k) {                       
                                                 return                                     (2 * k - (center[2] - center[0] - length));                       
                                                 }                       
           
                                                 // Case 3                       
                                                 else                       
                                                 return                                     length;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     center[3] = { 1, 2, 3 };                       
                                                 int                                     L = 1;                       
                                                 int                                     K = 1;                       
                                                 cout << max_intersection(center, L, K);                       
                         }                       

JAVA

                         // Java implementation                       
                         // of above approach                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to print the                       
                         // maximum intersection                       
                         static                                     int                                     max_intersection(                                     int                                     center[],                       
                                                 int                                     length,                                     int                                     k)                       
                         {                       
                                                 Arrays.sort(center);                       
           
                                                 // Case 1                       
                                                 if                                     (center[                                     2                                     ] - center[                                     0                                     ] >=                                     2                                     * k + length)                       
                                                 {                       
                                                 return                                     0                                     ;                       
                                                 }                       
           
                                                 // Case 2                       
                                                 else                                     if                                     (center[                                     2                                     ] - center[                                     0                                     ] >=                                     2                                     * k)                       
                                                 {                       
                                                 return                                     (                                     2                                     * k - (center[                                     2                                     ] -                       
                                                 center[                                     0                                     ] - length));                       
                                                 }                       
           
                                                 // Case 3                       
                                                 else                       
                                                 return                                     length;                       
                         }                       
           
                         // Driver Code                       
                         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));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Arnab Kundu                       

Python3

                         # Python3 implementation of above approach                       
           
                         # Function to print the maximum intersection                       
                         def                                     max_intersection(center, length, k):                       
           
                                                 center.sort();                       
           
                                                 # Case 1                       
                                                 if                                     (center[                                     2                                     ]                                     -                                     center[                                     0                                     ] >                                     =                                     2                                     *                                     k                                     +                                     length):                       
                                                 return                                     0                                     ;                       
           
                                                 # Case 2                       
                                                 elif                                     (center[                                     2                                     ]                                     -                                     center[                                     0                                     ] >                                     =                                     2                                     *                                     k):                       
                                                 return                                     (                                     2                                     *                                     k                                     -                                     (center[                                     2                                     ]                                     -                                     center[                                     0                                     ]                                     -                                     length));                       
           
                                                 # Case 3                       
                                                 else                                     :                       
                                                 return                                     length;                       
           
                         # Driver Code                       
                         center                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ];                       
                         L                                     =                                     1                                     ;                       
                         K                                     =                                     1                                     ;                       
                         print                                     (max_intersection(center, L, K));                       
           
                         # This code is contributed                       
                         # by mits                       

C#

                         // C# implementation                       
                         // of above approach                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to print the                       
                         // maximum intersection                       
                         static                                     int                                     max_intersection(                                     int                                     []center,                       
                                                 int                                     length,                                     int                                     k)                       
                         {                       
                                                 Array.Sort(center);                       
           
                                                 // Case 1                       
                                                 if                                     (center[2] - center[0] >= 2 * k + length)                       
                                                 {                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // Case 2                       
                                                 else                                     if                                     (center[2] -                       
                                                 center[0] >= 2 * k)                       
                                                 {                       
                                                 return                                     (2 * k - (center[2] -                       
                                                 center[0] - length));                       
                                                 }                       
           
                                                 // Case 3                       
                                                 else                       
                                                 return                                     length;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     []center = { 1, 2, 3 };                       
                                                 int                                     L = 1;                       
                                                 int                                     K = 1;                       
                                                 Console.WriteLine(max_intersection(center, L, K));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Subhadeep Gupta                       

PHP

                         <?php                       
                         // PHP implementation                       
                         // of above approach                       
           
                         // Function to print the                       
                         // maximum intersection                       
                         function                                     max_intersection(                                     $center                                     ,                       
                                                 $length                                     ,                                     $k                                     )                       
                         {                       
                                                 sort(                                     $center                                     );                       
           
                                                 // Case 1                       
                                                 if                                     (                                     $center                                     [2] -                       
                                                 $center                                     [0] >= 2 *                                     $k                                     +                                     $length                                     )                       
                                                 {                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // Case 2                       
                                                 else                                     if                                     (                                     $center                                     [2] -                       
                                                 $center                                     [0] >= 2 *                                     $k                                     )                       
                                                 {                       
                                                 return                                     (2 *                                     $k                                     - (                                     $center                                     [2] -                       
                                                 $center                                     [0] -                                     $length                                     ));                       
                                                 }                       
           
                                                 // Case 3                       
                                                 else                       
                                                 return                                     $length                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $center                                     =                                     array                                     (1, 2, 3);                       
                         $L                                     = 1;                       
                         $K                                     = 1;                       
                         echo                                     max_intersection(                                     $center                                     ,                                     $L                                     ,                                     $K                                     );                       
           
                         // This code is contributed                       
                         // by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript implementation                       
                         // of above approach                       
           
                         // Function to print the                       
                         // maximum intersection                       
                         function                                     max_intersection(center,length, k)                       
                         {                       
                                                 center.sort();                       
                                   
                                                 // Case 1                       
                                                 if                                     (center[2] - center[0] >= 2 * k + length)                       
                                                 {                       
                                                 return                                     0;                       
                                                 }                       
                                   
                                                 // Case 2                       
                                                 else                                     if                                     (center[2] - center[0] >= 2 * k)                       
                                                 {                       
                                                 return                                     (2 * k - (center[2] -                       
                                                 center[0] - length));                       
                                                 }                       
                                   
                                                 // Case 3                       
                                                 else                       
                                                 return                                     length;                       
                         }                       
                                   
           
                         // driver program                       
                                   
                                                 let center = [ 1, 2, 3 ];                       
                                                 let L = 1;                       
                                                 let K = 1;                       
                                                 document.write( max_intersection(center, L, K));                       
                                   
                         </script>                       

输出：

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章