1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#!/usr/bin/env python
# Challenge 093
#
# TASK #1 > Max Points
# Submitted by: Mohammad S Anwar
# You are given set of co-ordinates @N.
#
# Write a script to count maximum points on a straight line when given
# co-ordinates plotted on 2-d plane.
#
# Example 1:
# |
# | x
# | x
# | x
# + _ _ _ _
#
# Input: (1,1), (2,2), (3,3)
# Output: 3
# Example 2:
# |
# |
# | x x
# | x
# | x x
# + _ _ _ _ _
#
# Input: (1,1), (2,2), (3,1), (1,3), (5,3)
# Output: 3
from __future__ import print_function
import sys
def eprint(*args, **kwargs):
print(*args, file=sys.stderr, **kwargs)
class Point:
"""hold a point in 2D space"""
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return "Point({},{})".format(self.x, self.y)
def get_points():
"""get points from sys.argv"""
if len(sys.argv) < 7 or (len(sys.argv) % 2) == 0:
eprint("Usage: ch-1.py x y x y x y ...")
sys.exit(1)
P = []
for i in range(1, len(sys.argv)-1, 2):
P.append(Point(int(sys.argv[i]), int(sys.argv[i+1])))
return P
def in_line(pi, pj, pk):
"""return true if the three points are in a line"""
# compute cross product
dxc = pk.x - pi.x;
dyc = pk.y - pi.y;
dxl = pj.x - pi.x;
dyl = pj.y - pi.y;
cross = dxc * dyl - dyc * dxl;
return True if cross == 0 else False
def max_in_line(P):
"""count max number of points in a line"""
max_count = 0
# for each pair
for i in range(0, len(P)-1):
for j in range(i+1, len(P)):
# check other points against pair
count = 0
for k in range(0, len(P)):
if in_line(P[i], P[j], P[k]):
count += 1
max_count = max(max_count, count)
return max_count
def solve():
P = get_points()
print(max_in_line(P))
solve()
|
