Advertisement
Iam_Sandeep

microsoft colllinear points

Aug 3rd, 2022
784
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.83 KB | None | 0 0
  1. from fractions import Fraction as fr
  2. f=math.factorial
  3. class Solution:
  4.     def maxPoints(self, points: List[List[int]]) -> int:
  5.         def ncr(n,r):
  6.             return f(n)//f(r)//f(n-r)
  7.         n=len(points)
  8.         slope = lambda x1,y1,x2,y2:(y2-y1)/(x2-x1)
  9.         d=defaultdict(set)
  10.         ans=0
  11.         if n==1:return 1
  12.         for i in range(n):
  13.             for j in range(i+1,n):
  14.                 x1,y1=points[i]
  15.                 x2,y2=points[j]
  16.                 if x1==x2:
  17.                     d[(inf,x1)].update({i,j})
  18.                 else:
  19.                     sp=fr(y2-y1,x2-x1)
  20.                     incept=y1-sp*x1
  21.                     d[(sp,incept)].update({i,j})
  22.         ans=0
  23.         for i in d.values():
  24.             t=len(i)
  25.             if t>=3:
  26.                 ans+=ncr(t,3)
  27.         return ans
  28.        
  29.        
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement