파이썬에서 한 줄에 있는 점의 수를 세는 프로그램

<시간/>

좌표 목록이 있다고 가정합니다. 각 좌표에는 데카르트 평면의 한 점을 나타내는 두 개의 값 x와 y가 있습니다. 이제 어떤 선에 있는 최대 점 수를 찾으십시오.

따라서 입력이 좌표 =[[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7과 같으면 ]], 점들이 선에 있는 [1, 1], [2, 2], [6, 6], [7, 7]]이므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

해상도 :=0
범위 0에서 포인트 목록 크기까지의 i에 대해
- (x1, y1) :=포인트[i]
- 슬로프 :=새 지도
- 동일 :=1
- 범위 i + 1에서 포인트 크기까지의 j에 대해 수행
  - (x2, y2) :=포인트[j]
  - x2가 x1과 같으면
    - 슬로프[inf] :=1 + (종료되면 슬로프[inf] 그렇지 않으면 0)
  - 그렇지 않으면 x1이 x2와 같고 y1이 y2와 같을 때
    - 동일 :=동일 + 1
  - 그렇지 않으면
    - 기울기 :=(y2 - y1) /(x2 - x1)
    - 기울기[기울기] :=1 + (나가면 기울기[기울기] 0)
- 슬로프가 비어 있지 않으면
  - res :=res의 최대값 및 (동일한 + 모든 기울기 값 목록의 최대값)
반환 해상도

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, points):
      res = 0
      for i in range(len(points)):
         x1, y1 = points[i][0], points[i][1]
         slopes = {}
         same = 1
         for j in range(i + 1, len(points)):
            x2, y2 = points[j][0], points[j][1]
            if x2 == x1:
               slopes[float("inf")] = slopes.get(float("inf"), 0) + 1
            elif x1 == x2 and y1 == y2:
               same += 1
            else:
               slope = (y2 - y1) / (x2 - x1)
               slopes[slope] = slopes.get(slope, 0) + 1
         if slopes:
            res = max(res, same + max(slopes.values()))
      return res
ob = Solution()
coordinates = [[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]
print(ob.solve(coordinates))

입력

[[6, 2],[8, 3],[10, 4],[1, 1],[2, 2],[6, 6],[7, 7]]