{
 "metadata": {
  "name": "",
  "signature": "sha256:183c9e17b73179464622911276d7e98d8c0d9fb2335ce136b293fe4f2d921f70"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"\"\"\n",
      "Archery problem: https://www.hackerrank.com/contests/quora-haqathon/challenges/archery\n",
      "\"\"\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "'\\nArchery problem: https://www.hackerrank.com/contests/quora-haqathon/challenges/archery\\n'"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Enter your code here. Read input from STDIN. Print output to STDOUT\n",
      "# radii = [1,2,3,4]\n",
      "def isQ(r,line):\n",
      "    x1,y1,x2,y2 = line\n",
      "    if y1 == y2 and x1 == x2:\n",
      "        #print \"Arrow of zero length.\"\n",
      "        return False\n",
      "    if x1 == x2:\n",
      "        y_sqr = (r**2 - c**2)\n",
      "        if y_sqr < 0:\n",
      "            #print \"No intersection\"\n",
      "            return False\n",
      "        y = y_sqr**0.5\n",
      "        if (y-y1)*(y-y2) <= 0 and (-y-y1)*(-y-y2) > 0:\n",
      "            #print \"Exactly one intersection with circle\"\n",
      "            return True\n",
      "        if (-y-y1)*(-y-y2) <= 0 and (y-y1)*(y-y2) > 0:\n",
      "            #print \"Exactly one intersection with circle\"\n",
      "            return True\n",
      "    m = (y1-y2)/(1.0*(x1-x2))\n",
      "    c = y1 -m*x1\n",
      "    a = (m**2+1)\n",
      "    b = 2*m*c\n",
      "    d = c**2 - r**2\n",
      "    #print \"Parameters (m,c,a,b,d): \", m,c,a,b,d\n",
      "    sqrt_t = b**2 - 4*a*d\n",
      "    #print \"SQRT_T\", sqrt_t\n",
      "    if sqrt_t < 0:\n",
      "        #print \"No intersection\"\n",
      "        return False\n",
      "    sqrt_t = sqrt_t ** 0.5\n",
      "    #print \"SQRT_T\", sqrt_t\n",
      "    x = (-b + sqrt_t)/(2*a)\n",
      "    y = m*x + c\n",
      "    count_p = 0\n",
      "    #print \"Intersection point: \",x , y\n",
      "    if (y-y1)*(y-y2) <= 0 and (x-x1)*(x-x2) <=0:\n",
      "        count_p += 1\n",
      "    x = (-b - sqrt_t)/(2*a)\n",
      "    y = m*x + c\n",
      "    #print \"Intersection point: \",x , y\n",
      "    if (y-y1)*(y-y2) <= 0 and (x-x1)*(x-x2) <=0:\n",
      "        count_p += 1\n",
      "    if count_p != 1:\n",
      "        #print \"More than one intersection with circle\", count_p\n",
      "        return False\n",
      "    return True\n",
      "            \n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isQ(1,(1,1,0,0))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def calcQ(radii, lines):\n",
      "    count = 0\n",
      "    for r in radii:\n",
      "        r = r**2\n",
      "        for line in lines:\n",
      "            x1,y1,x2,y2 = line\n",
      "            min_r = min(((x1**2)+(y1**2)), ((x2**2)+(y2**2)))\n",
      "            if min_r > r:\n",
      "                print \"All points beyond this are discarded\", r, line\n",
      "                break\n",
      "            max_r = max(((x1**2)+(y1**2)), ((x2**2)+(y2**2)))\n",
      "            if r!= min_r and r != max_r and (r-min_r)*(r-max_r) > 0:\n",
      "                print \"Outside range: \", r, min_r, max_r, line\n",
      "                continue\n",
      "            count += 1\n",
      "            #if isQ(r,line):\n",
      "                #count += 1\n",
      "    return count"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 57
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = int(input())\n",
      "radii = [int(k) for k in raw_input().split()]\n",
      "lines = []\n",
      "n = int(input())\n",
      "for i in range(n):\n",
      "    lines.append([int(k) for k in raw_input().split()])\n",
      "print calcQ(radii,lines)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 2 3 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 -1 4 -3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2 1 1 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 -2 3 -4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = int(input())\n",
      "radii = [int(k) for k in raw_input().split()]\n",
      "radii = sorted(radii)\n",
      "#print radii\n",
      "lines = []\n",
      "n = int(input())\n",
      "for i in range(n):\n",
      "    lines.append([int(k) for k in raw_input().split()])\n",
      "lines.sort(key=lambda x: min(((x[0]**2)+(x[1]**2)), ((x[2]**2)+(x[3]**2))))\n",
      "print lines\n",
      "print calcQ(radii,lines)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 2 3 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 -1 4 -3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2 1 1 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 -2 3 -4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[[1, -1, 4, -3], [2, 1, 1, 2], [1, -2, 3, -4]]\n",
        "All points beyond this are discarded 1 [1, -1, 4, -3]\n",
        "All points beyond this are discarded 4 [2, 1, 1, 2]\n",
        "Outside range:  9 5 5 [2, 1, 1, 2]\n",
        "Outside range:  16 5 5 [2, 1, 1, 2]\n",
        "5\n"
       ]
      }
     ],
     "prompt_number": 58
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = int(input())\n",
      "radii = [int(k) for k in raw_input().split()]\n",
      "radii = sorted(radii)\n",
      "#print radii\n",
      "lines = []\n",
      "n = int(input())\n",
      "for i in range(n):\n",
      "    lines.append([int(k) for k in raw_input().split()])\n",
      "print calcQ(radii,lines)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 2 3 4\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 -1 4 -3\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2 1 1 2\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1 -2 3 -4\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Outside range:  1 [1, -1, 4, -3]\n",
        "Outside range:  1 [2, 1, 1, 2]\n",
        "Outside range:  2 [2, 1, 1, 2]\n",
        "Outside range:  3 [2, 1, 1, 2]\n",
        "Outside range:  4 [2, 1, 1, 2]\n",
        "Outside range:  1 [1, -2, 3, -4]\n",
        "Outside range:  2 [1, -2, 3, -4]\n",
        "Outside range:  3 [1, -2, 3, -4]\n",
        "Makes Q\n",
        "Outside range:  4 [1, -2, 3, -4]\n",
        "Makes Q\n",
        "5\n"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}