fork download
copy 
  1. def parse(inFile):
  2.     [H,W,D] = inFile.getInts()
  3.     return (H,W,D,[inFile.readline() for k in xrange(H)])
  4.  
  5. from fractions import Fraction, gcd
  6.  
  7. def cansee((H,W),(x,y),(dx,dy),D,grid):
  8.     if (dy < 0):
  9.         return cansee((H,W),(x,(W - 1 - y)),(dx,-dy),D,[z[::-1] for z in grid])
  10.     if (dx < 0):
  11.         return cansee((H,W),((H - 1 - x),y),(-dx,dy),D,grid[::-1])
  12.     if (dx == 0) and (dy == 1):
  13.         z = y + 1
  14.         while grid[x][z] == ".":
  15.             z = z + 1
  16.         return (2 * (z - y) - 1) <= D
  17.     if (dy == 0) and (dx == 1):
  18.         z = x + 1
  19.         while grid[z][y] == ".":
  20.             z = z + 1
  21.         return (2 * (z - x) - 1) <= D
  22.     kk = 1
  23.     while ((kk + 1) * (kk + 1)) * (dx * dx + dy * dy) <= D * D:
  24.         kk += 1
  25.     horizontalIntersections = [[Fraction(2*k-1,2*dx),0] for k in xrange(1,dx+1)]
  26.     verticalIntersections = [[Fraction(2*k-1,2*dy),1] for k in xrange(1,dy+1)]
  27.     if (dx & dy & 1):
  28.         half = Fraction(1,2)
  29.         ints = [z for z in horizontalIntersections if z[0] != half] + [z for z in verticalIntersections if z[0] != half] + [[half,2]]
  30.     else:
  31.         ints = horizontalIntersections+verticalIntersections
  32.     if True:
  33.         ints.sort()
  34.         posn = (Fraction(2*x+1,2),Fraction(2*y+1,2))
  35.         dirn = (dx, dy)
  36.         timeAt = 0
  37.         for m in xrange(kk):
  38.             for isn in ints:
  39.                 dt = isn[0] - timeAt
  40.                 timeAt = isn[0]
  41.                 posn = (posn[0] + dirn[0] * dt, posn[1] + dirn[1] * dt)
  42.                 (xat,yat) = (int(posn[0]),int(posn[1]))
  43.                 if (isn[1] == 0):
  44.                     if (dirn[0] > 0) and grid[xat][yat] == "#":
  45.                         dirn = (-dirn[0],dirn[1])
  46.                     elif (dirn[0] < 0) and grid[xat-1][yat] == "#":
  47.                         dirn = (-dirn[0],dirn[1])
  48.                 elif (isn[1] == 1):
  49.                     if (dirn[1] > 0) and grid[xat][yat] == "#":
  50.                         dirn = (dirn[0],-dirn[1])
  51.                     elif (dirn[1] < 0) and grid[xat][yat-1] == "#":
  52.                         dirn = (dirn[0],-dirn[1])
  53.                 elif (isn[1] == 2):
  54.                     nowx =  xat if (dirn[0] < 0) else (xat - 1)
  55.                     nextx = (xat - 1) if (dirn[0] < 0) else xat
  56.                     nowy =  yat if (dirn[1] < 0) else (yat - 1)
  57.                     nexty = (yat - 1) if (dirn[1] < 0) else yat
  58.                     up = grid[nextx][nowy] == "#"
  59.                     right = grid[nowx][nexty] == "#"
  60.                     ur = grid[nextx][nexty] == "#"
  61.                     assert(grid[nowx][nowy] != "#")
  62.                     if ur:
  63.                         if up:
  64.                             if right:
  65.                                 dirn = (-dirn[0], -dirn[1])
  66.                             else:
  67.                                 dirn = (-dirn[0], dirn[1])
  68.                         else:
  69.                             if right:
  70.                                 dirn = (dirn[0], -dirn[1])
  71.                             else:
  72.                                 return False
  73.             dt = 1 - timeAt
  74.             timeAt = 0
  75.             posn = (posn[0] + dirn[0] * dt, posn[1] + dirn[1] * dt)
  76.             if (posn == (Fraction(2*x+1,2),Fraction(2*y+1,2))):
  77.                 return True
  78.     return False
  79.  
  80. def solve((H,W,D,grid)):
  81.     count = 0
  82.     (x,y) = [(i,j) for i in xrange(H) for j in xrange(W) if grid[i][j] == "X"][0]
  83.     for dx in xrange(-D,D+1):
  84.         for dy in xrange(-D,D+1):
  85.             if (dx * dx + dy * dy) <= D * D and abs(gcd(dx,dy)) == 1:
  86.                 if cansee((H,W),(x,y),(dx,dy),D,grid):
  87.                     count += 1
  88.     return count
  89.  
  90. if __name__ == "__main__":
  91.     from GCJ import GCJ
  92.     GCJ(parse, solve, "/Users/lpebody/gcj/2012_q/", "d").run()
  93.  
  94.  
  95.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PCn82
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!