좌표평면상에서 x좌표와 y좌표가 모두 정수인 점들을 격자점이라고 하자. 이 때, 2개의 서로 다른 격자점의 좌표를 입력받아 그 두 점을 잇는 선분이 지나는 격자점을 모두 출력하는 프로그램을 작성하시오. 입력방식은 자유로이 설정한다.
입력예1
[-2, 0],[0,2]
출력예1
[-1,1]
입력예2
[0,0],[0,3]
출력예2
[0,1], [0,2]
입력예3
[0,0],[1,-2]
출력예3
None
16개의 풀이가 있습니다.
def get_lattice_point(p1, p2):
p = []
a = (-1, 1)[p1[0] < p2[0]]
b = (-1, 1)[p1[1] < p2[1]]
if p1[0]-p2[0] == 0:
for y in range(p1[1], p2[1]+b, b):
p.append([0, y])
else:
m = (p1[1]-p2[1])/(p1[0]-p2[0])
n = p1[1] - (m * p1[0])
for x in range(p1[0], p2[0]+a, a):
for y in range(p1[1], p2[1]+b, b):
if y == m*x + n: p.append([x, y])
return p[1:-1]
머리가 빙글빙글
Python 3.7
def main():
p0, p1 = eval(input())
xmin, xmax = min(p0[0], p1[0]), max(p0[0], p1[0])
ymin, ymax = min(p0[1], p1[1]), max(p0[1], p1[1])
rst = []
if xmin != xmax:
for x in range(xmin + 1, xmax):
y = (p1[1] - p0[1]) / (p1[0] - p0[0]) * (x - p0[0]) + p0[1]
if y == int(y):
rst.append(str([x, int(y)]))
else: # y = const 직선인 경우
for y in range(ymin + 1, ymax):
rst.append(str([xmin, y]))
print(", ".join(rst) if rst else None)
if __name__ == "__main__":
main()
from collections import namedtuple
P = namedtuple('P', 'x y')
grd = lambda n, m: str((n.y - m.y) / (n.x - m.x)) if n.x - m.x else 'inf'
ans = []
A, B = P(-2, 0), P(0, 2)
for x in range(min(A.x, B.x), max(A.x, B.x)+1):
for y in range(min(A.y, B.y), max(A.y, B.y)+1):
C = P(x, y)
if C not in (A, B) and grd(A, C) == grd(C, B):
ans.append(tuple(C))
print(*ans if ans else None)
def gcd(n,m):
if m>n:
n,m=m,n
if m==0:
return n
n=n%m
return gcd(m,n)
a=input('a 좌표입력(x,y): ').split(',')
b=input('b 좌표입력(x,y): ').split(',')
a=list(map(int,a))
b=list(map(int,b))
dx=b[0]-a[0]
dy=b[1]-a[1]
ddx=dx/gcd(abs(dx),abs(dy))
ddy=dy/gcd(abs(dx),abs(dy))
a[0]=a[0]+ddx
a[1]=a[1]+ddy
while a!=b:
print('%d,%d'%(a[0],a[1]))
a[0]=a[0]+ddx
a[1]=a[1]+ddy
Python 3.7 사용
from math import gcd
p1 = [-2,0]
p2 = [0,2]
p3=[0,0]
p4=[0,3]
p5=[0,0]
p6 = [1,-2]
def slope(point1, point2): # computes the privitive directional vector with its multiplicity
direc = [point1[0]-point2[0], point1[1]-point2[1]]
m = gcd(direc[0],direc[1]) # multiplicity of the slope
return [int(direc[0]/m), int(direc[1]/m), m]
def lattice(point1,point2): # computes lattice pts betw point1 and point2
lpoints_bet = [] # placeholder list of lattice vectors bet point1 and point2
s = slope(point1,point2)
if s[2] != 1: # if the multiplicity is greater than 1
for i in range(1,s[2]):
lpoints_bet += [[point2[0]+ i* s[0],point2[1]+i*s[1]]]
return lpoints_bet
else:
return "None"
print(lattice(p1,p2))
print(lattice(p3,p4))
print(lattice(p5,p6))
package main
import "fmt"
type DoubleCoord struct {
c [2][2]int
d [2]int
}
func newDoubleCoord(a, b [2]int) DoubleCoord {
obj := DoubleCoord{}
obj.c[0] = a
obj.c[1] = b
obj.reduction()
return obj
}
func (obj *DoubleCoord) reduction() {
for i := 0; i < 2; i++ {
obj.d[i] = obj.c[1][i] - obj.c[0][i]
}
t := gcd(abs(obj.d[0]), abs(obj.d[1]))
for i := 0; i < 2; i++ {
obj.d[i] /= t
}
}
func (obj *DoubleCoord) solve() (res [][2]int) {
tmp := obj.c[0]
for {
tmp[0] += obj.d[0]
tmp[1] += obj.d[1]
if ((tmp[0]-obj.c[0][0])*(tmp[0]-obj.c[1][0]) > 0) || ((tmp[1]-obj.c[0][1])*(tmp[1]-obj.c[1][1]) > 0) || tmp == obj.c[1] {
break
} else {
res = append(res, tmp)
}
}
fmt.Println(res)
return res
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}
func gcd(a, b int) int {
for b != 0 {
r := a % b
a, b = b, r
}
return a
}
func main() {
x := newDoubleCoord([2]int{-2, 0}, [2]int{0, 2})
x.solve()
}
Ruby
fn(x) = [x, x * 기울기], (x1+1...x2)구간에서 fn(x)가 정수인 걸 출력. 입력된 두 점의 x값이 같으면 fn(y)로 계산
KEY_IN = -> { gets.split.map(&:to_i) }
def find_crossed_in_segment(from: KEY_IN.call, to: KEY_IN.call)
x1, x2, y1, y2 = *from.zip(to).sum([], &:minmax)
fn = ->x1,x2,y1,y2 { (x1+1...x2).map { |x| [x, x * (y2-y1)/(x2-x1).to_f] } }
crossed = y1 == y2 ? fn[x1,x2, y1,y2] : fn[y1,y2, x1,x2].map(&:rotate)
grid = ->point { (point.first % 1 + point.last % 1) == 0 }
result = crossed.select(&grid).map { |point| point.map(&:to_i) }
puts result.size, (result.empty? ? 'None' : result.map(&:inspect).join(', '))
end
Test
# from stdin case
$stdin = StringIO.new("-2 0\n0 2")
expect { find_crossed_in_segment }.to output("1\n[1, 1]\n").to_stdout
# cases : sloped, x axis, none, y axis
expect { find_crossed_in_segment from: [-2, 0], to: [0, 2] }
.to output("1\n[1, 1]\n").to_stdout
expect { find_crossed_in_segment from: [0, 0], to: [0, 3] }
.to output("2\n[0, 1], [0, 2]\n").to_stdout
expect { find_crossed_in_segment from: [0, 0], to: [1, -2] }
.to output("0\nNone\n").to_stdout
expect { find_crossed_in_segment from: [4, 0], to: [-2, 0] }
.to output("5\n[-1, 0], [0, 0], [1, 0], [2, 0], [3, 0]\n").to_stdout
from sympy import *
import re
num_com, points, result = re.compile("[-]?\d*\.?\d+"), [], []
points.append(num_com.findall(input("p1 : ")))
points.append(num_com.findall(input("p2 : ")))
if points[0][0] == points[1][0] :
for i in range(min(int(points[0][1])+1, int(points[1][1])), max(int(points[0][1]), int(points[1][1]))) :
result.append([int(points[0][0]), i])
print(result)
else :
fn = ((int(points[0][1])-int(points[1][1]))/(int(points[0][0])-int(points[1][0])))*(x-int(points[0][0]))+int(points[0][1])
for m in range(min(int(points[0][0])+1, int(points[1][0])), max(int(points[0][0]), int(points[1][0]))) :
if fn.subs(x, m) % 1 == 0 :
result.append([m, int(fn.subs(x, m))])
print(result)
결과
p1 : -1 0
p2 : 4 0
[[0, 0], [1, 0], [2, 0], [3, 0]]
p1 : 0 0
p2 : 8, 4
[[2, 1], [4, 2], [6, 3]]
n1=list(map(int,input("첫번째 좌표를 입력하십시오: ").split(",")))
n2=list(map(int,input("두번째 좌표를 입력하십시오: ").split(",")))
try:
an=(n2[1]-n1[1])/(n2[0]-n1[0]) #n1과 n2를 직선으로 이었을 때의 기울기
except:
an=0 #x좌표가 둘 다 0이거나 둘 다 같거나 할 시 나눠지지 않으므로 an=0이라 지정
#어느 한 점에서 다른 한 점으로의 기울기가 같다면 그 선분위에 있는 점이다.
xlst=[] #정수 x좌표를 받기 위한 빈 리스트
if n1[0]==n2[0]: #n1과 n2의 x좌표가 같다면 xlst는 n1[0](또는 n2[0]) 하나를 가짐
xlst.append(n1[0])
ylst=[] #정수 y좌표를 받기 위한 빈 리스트
if n1[1]==n2[1]: #n1과 n2의 y좌표가 같다면 ylst는 n1[1](또는 n2[1]) 하나를 가짐
ylst.append(n1[1])
elst=[] #좌표[x,y]를 받기 위한 빈 리스트
for x in range(min(n1[0],n2[0])+1,max(n1[0],n2[0])): #n1과 n2의 x좌표 중 작은 것부터 큰 것까지 범위를 지정
xlst.append(x)
for y in range(min(n1[1],n2[1])+1,max(n1[1],n2[1])): #n1과 n2의 y좌표 중 작은 것부터 큰 것까지 범위를 지정
ylst.append(y)
for xnum in xlst:
for ynum in ylst:
try:
if (n2[1]-ynum)/(n2[0]-xnum)==an: #[xnum,ynum]에서 n1(또는 n2)까지의 기울기(n2와 n1)가 같으면 elst에 추가
elst.append([xnum,ynum])
except:
elst.append([xnum,ynum]) #n1, n2 둘 다 x축, 또는 y축으로 평행하면 기울기가 의미가 없으므로 그냥 추가
if len(elst)==0: #elst의 길이가 0이면(elst에 정수 좌표가 담기지 않으면) None을 출력
print("None")
else:
print(elst)
x=str(input('x1 y1 x2 y2....')).split(' ')
x1,y1,x2,y2=int(x[0]),int(x[1]),int(x[2]),int(x[3])
print('(',x1,',',y1,')','(',x2,',',y2,')')
n=0
if not x2==x1:
a=(y2-y1)/(x2-x1)
b=y1-(a*x1)
for i in range (x1+1,x2):
if int(a*i+b)==a*i+b:
print ('(',i,',',int(a*i+b),')',end='')
n+=1
else:
for i in range (y1+1,y2):
print ('(',x1,',',i,')',end='')
n+=1
if n==0:
print('None')
def grid(inp):
x_var = inp[1][0] - inp[0][0]
y_var = inp[1][1] - inp[0][1]
if x_var == 1 or y_var == 1:
print('None')
elif x_var == 0:
for i in range(inp[0][1]+1, inp[1][1]):
print('[{}, {}]'.format(inp[0][0], i), end=' ')
elif y_var == 0:
for i in range(inp[0][0]+1, inp[1][0]):
print('[{}, {}]'.format(inp[0][1], i), end=' ')
else:
intercept = inp[0][1] - ((y_var/x_var)*inp[0][0])
for x in range(inp[0][0]+1, inp[1][0]):
y = (y_var/x_var)*x + intercept
print('[{}, {}]'.format(x, int(y)))
if __name__ == '__main__':
inp = [[0,0],[1,-2]]
grid(inp)
p1 = list(map(int, input("p1 : ").split(', ')))
p2 = list(map(int, input("p2 : ").split(', ')))
output = []
if p1[0] == p2[0]:
for j in range(p1[1]+1, p2[1]):
output.append([p1[0], j])
else:
if p1[0] > p2[0]:
p1, p2 = p2, p1
y_spd = (p2[1]-p1[1]) / (p2[0]-p1[0])
for i in range(1, p2[0]-p1[0]):
if y_spd*i == int(y_spd*i):
x = int(p1[0] + i)
y = int(p1[1] + y_spd* i)
output.append([x, y])
if len(output) == 0:
print("none")
else:
print(output)
a1 = input("첫번쨰 격자점은?").split(',')
a2 = input("두번쨰 격자점은?").split(',')
x1 = int(a1[0])
y1 = int(a1[1])
x2 = int(a2[0])
y2 = int(a2[1])
arr=[]
if x2==x1:
for k in range(y1+1,y2):
arr.append([x1,k])
elif y2==y1:
for k in range(x1+1,x2):
arr.append([k,y2])
else:
slope = (y2-y1)/(x2-x1)
x_inter = y2-slope*x2
for k in range(x1+1,x2):
if slope*k+x_inter == int(slope*k+x_inter):
arr.append([k,int(slope*k+x_inter)])
if len(arr)==0:
print("None")
else:
for i in arr:
print(i,end=', ')
기울기가 0일떄/ 기울기가 무한대일때/그외일떄 이렇게 3가지 경우로 나눠서 코드를 짰고, 1차 함수를 이용했어요 입력값 범위내에서 정수 x를 대입했을떄 y도 정수로 나오는 쌍을 arr 리스트화 했습니다
// Rust
// 두 point 간 가로, 세로 이동 거리의 gcd를 구해, 이동 시 정수 격자가 나올 수 있는 unit 이동 벡터를 구합니다
fn grid_point() {
let inputs = [((-2, 0), (0, 2)),
((0, 0), (0, 3)),
((0, 0), (1, -2))];
for input in inputs {
println!("\n{:?}", input);
// 첫번재 격자점을 원점으로 생각할 때, 두 번째 격자점 위치 (a, b)
let a: i32 = input.1.0-input.0.0;
let b: i32 = input.1.1-input.0.1;
// 정수 격자점을 지나기 위한 최소 이동 unit
let g = gcd(a.abs() as u128, b.abs() as u128) as i32;
let unit = (a / g, b / g);
// 다음 정수 격자점
let mut next: (i32, i32) = (0, 0);
while next.0.abs() < (a-unit.0).abs() || next.1.abs() < (b-unit.1).abs() {
next = (next.0 + unit.0, next.1 + unit.1);
println!(" {:?}", (next.0 + input.0.0, next.1 + input.0.1));
}
}
} fn gcd(a_: u128, b_: u128) -> u128 {
let mut a = a_;
let mut b = b_;
if a < b { let t = b;
b = a;
a = t;}
while b != 0 { let t = a;
a = b;
b = t % b;}
a
}
[x1,y1], [x2, y2] =[0,0],[1,-2]
if x1 == x2:
sign = int((y2-y1)/abs(y2-y1))
for y in range(y1+sign, y2, sign):
dots.append([x1, y])
elif x2 > x1:
slope = (y2-y1)/(x2-x1)
for x in range(x1+1, x2):
y = y1+(x-x1)*slope
if y == int(y):
dots.append([ x, int(y)])
elif x2 < x1:
slope = (y2-y1)/(x2-x1)
for x in range(x1-1, x2,-1):
y = y1+(x-x1)*slope
if y == int(y):
dots.append([ x, int(y)])
if len(dots) > 0:
print(dots)
else:
print('None')
def coordinates(p1, p2):
dx, dy = p1[0] - p2[0], p1[1]-p2[1]
lx = min(p1[0], p2[0])
ly = min(p1[1], p2[1])
p = []
for x in range(lx, p1[0]+p2[0]-lx+1):
for y in range(ly+1, p1[1]+p2[1]-ly):
if (x-p1[0])*dy - (y-p1[1])*dx == 0:
p.append([x,y])
print(p)
coordinates([-2, 0], [0, 2])
coordinates([0, 0], [0, 3])
coordinates([0, 0], [1, -2])