PROSAGA码农传奇-pascal-点数最多两条线？

0# 甲基蓝 | 2019-08-31 10-32

1# 哇塞 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    我想Q的答案应该分为两部分。
  
  
    I.如何知道给定的三个点属于同一条线？
问题的这一部分的答案由@Lurd给出，然后由Mbo扩展。
让我们说出他们的解决方案
     <code>
 function BelongToOneLine(Pnts: array [1..3] of TPoint): boolean;
 </code>
     我们可以认为这部分已经解决。
  
  
    II。如何减少算法的时间消耗，换句话说：如何避免调用
     <code>
 BelongToOneLilne
 </code>
     每个可能的点组合作为参数？
  
  
    这是算法。
  
  <OL>
    <LI>
      
        我们选择5
        
          不同
        
         任务集中的点。 5就够了（检查组合可能性）。
      
    </LI>
    <LI>
      
        我们找到问题的答案，如果给定的五个中至少有三个点属于一条线。
      
      
        
          如果不 -
        
         然后我们不需要迭代其余的点 - 答案是我们需要两行以上。
      
      
        
          如是 -
        
         （假设Pt1，Pt2和Pt3属于同一条线，而Pt4和Pt5则不属于同一条线）。
      
    </LI>
    <LI>
      
        然后，我们将不属于Pt1-Pt2-Pt3线的点存储在不同的“局外人”点阵列中（或将其索引存储在主阵列中）。它可能有
         <code>
 Length = 0
 </code>
         到这一步结束。这不会影响算法的其余部分。
      
    </LI>
    <LI>
      
        我们得到函数的布尔结果
         <code>
 BelongToOneLine([Pt1, Pt2, Pt[i]])
 </code>
        。
      
      
        
          如是 -
        
         我们跳过这一点 - 它属于Pt1-Pt2-Pt3线。
      
      
        
          如果不 -
        
         我们将这一点存储在“局外人”数组中。
      
    </LI>
    <LI>
      
        我们观察OutsidersArray的长度。
      
      
        
          如果是＆lt; = 2
        
         那么整个Q的答案是肯定的，它们确实属于2行或更少行。
      
      
        
          如果> 2
        
         然后我们迭代函数
         <code>
 BelongToOneLine([OutsiderPt1, OutsiderPt2, OutsiderPt[i]])
 </code>
         直到高（OutsiderArray）或直到何时
         <code>
 OutsiderPt[i]
 </code>
         不属于OutsiderPt1-OutsiderPt2行。 OutsiderArray的所有点必须属于同一行，否则整个Q的答案将为负。
      
    </LI>
  </醇>
  
    
      数学笔记
    
  
  
    如果没有优化，就会有不合理的数量
     <code>
 n! / ((n - k)! * k!)
 </code>
    。
通过优化，它将是：

<code>
 5! / ((5-3)! * 3!)
 </code>
     +
     <code>
 (n - 3)
 </code>
     +
     <code>
 P(q)outsiders * n
 </code>
     对于n = 10000，大约是15000.大多数负数 - 大约20000。
  
  
    
      另一个优化说明
    
  
  
    用整数变量替换TPoint的声明。
  
</DIV>

2# 庸人自扰1 | 2019-08-31 10-32