from fractions import Fraction as F
from math import gcd
import itertools
def edges(poly): return [(poly[i],poly[(i+1)%len(poly)]) for i in range(len(poly))]
def reflect(d,a,b):
    ex,ey=b[0]-a[0],b[1]-a[1]
    dx,dy=d
    if ey==0: return (dx,-dy)
    if ex==0: return (-dx,dy)
    if ex*ey>0: return (dy,dx)
    return (-dy,-dx)
def cross(ax,ay,bx,by): return ax*by-ay*bx
def trace(poly,S,d,D,maxsteps=100000):
    """exact: returns 'lit','corner','loop'"""
    E=edges(poly); V=set(tuple(map(F,v)) for v in poly)
    P=(F(S[0]),F(S[1])); seen=set(); path=[P]; last=None
    for _ in range(maxsteps):
        best=None
        for i,(a,b) in enumerate(E):
            if i==last: continue
            ex,ey=b[0]-a[0],b[1]-a[1]
            den=cross(d[0],d[1],ex,ey)
            if den==0: continue
            wx,wy=a[0]-P[0],a[1]-P[1]
            t=F(cross(wx,wy,ex,ey),den); u=F(cross(wx,wy,d[0],d[1]),den)
            if t<=0 or u<0 or u>1: continue
            if best is None or t<best[0]: best=(t,i,u)
        t,i,u=best
        Q=(P[0]+t*d[0],P[1]+t*d[1])
        # D on segment P->Q ?
        wx,wy=D[0]-P[0],D[1]-P[1]
        if cross(wx,wy,d[0],d[1])==0:
            s=F(wx*d[0]+wy*d[1], d[0]*d[0]+d[1]*d[1])
            if 0<s<=t: path.append((F(D[0]),F(D[1]))); return 'lit',path
        path.append(Q)
        if u==0 or u==1: return 'corner',path
        st=(i,Q,d)
        if st in seen: return 'loop',path
        seen.add(st)
        d=reflect(d,*E[i]); P=Q; last=i
    return 'max',path
def dirs(N):
    out=[]
    for p in range(-N,N+1):
        for q in range(-N,N+1):
            if (p or q) and gcd(abs(p),abs(q))==1: out.append((p,q))
    return out
def check(poly,S,D,N):
    from collections import Counter
    c=Counter(); lit=[]
    for d in dirs(N):
        r,_=trace(poly,S,d,D); c[r]+=1
        if r=='lit': lit.append(d)
    return c,lit
if __name__=='__main__':
    # L room of unit squares, lattice integer
    room=[(0,0),(4,0),(4,2),(2,2),(2,4),(0,4)]
    print(check(room,(1,1),(3,1),12))   # same parity
    print(check(room,(1,1),(1,3),12))
    print(check(room,(1,1),(2,1),12))   # other class