Find out if a point is inside a circle in a Cartesian plane

Question

Find out if a point is inside a circle in a Cartesian plane

Navigation

#1 by (1 votes)

2

I was doing the Target Shooting task of the 2013 Olympiad of Computing (OBI) level 2, which can be found here , and I was able to do without great difficulties. The task was to figure out how many points a person would make by shooting at a target, considering that she would gain one point at each circumference that each shot was internal or belonged. The input of the program consists of the number of circles (all whose center is in (0,0)) and their rays and the number of shots and their coordinates. The output is just the number of points the person would make.

Well, so far so good - my code works. The problem is that in the official OBI tester, which can be found here , I received many results with timeout exceeded and I ended up with only 20 points out of 100 possible. I wanted help, therefore, to improve the performance of my program.

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

def calcula_pontos():
    qtd_circulos, qtd_tiros = raw_input().split()
    raios_circulos = [float(raw_input()) for circulo in range(int(qtd_circulos))]
    cord_tiros = [raw_input().split() for tiro in range(int(qtd_tiros))]
    pontos = 0
    for x, y in cord_tiros:
        for raio in raios_circulos:
            if((int(x) ** 2) + (int(y) ** 2) > (raio ** 2)):
                continue
            else:
                pontos += 1
    print pontos

calcula_pontos()

desempenho python runtime python-2.7

asked by anonymous 24.04.2016 / 23:19

1 answer

The predict () function does not accept exponential regression in R How to list in the listView the results of MySql

score 1 · Answer 1

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

def calcula_pontos():

    def closure_dist2_tiro_centro():
        input = raw_input().split()
        return (int(input[0]) ** 2) + (int(input[0]) ** 2)

    qtd_circulos, qtd_tiros = raw_input().split()
    raios2_circulos = [(float(raw_input()) ** 2) for circulo in range(int(qtd_circulos))]
    dist2_tiros = [closure_dist2_tiro_centro() for tiro in range(int(qtd_tiros))]

    pontos = 0
    for tiro in dist2_tiros:
        for idx,raio in enumerate(raios2_circulos):
            if tiro < raio:
                pontos += (len(raios2_circulos) - idx)
                break
    print pontos

calcula_pontos()

The above code takes into account two optimizations:

The data is calculated as soon as possible, in the understanding of the input list
The second list is iterated as little as possible, considering that if a shot has a distance smaller than the radius of one of the circles, it has it for all the following