0
\$\begingroup\$

I am an average coder trying to improve my Python by doing solved problems in it.

One of the problem I did is this, here is the code I tried which I have based on the official solution:

def area(A, B, C):
  return float((x[B] - x[A])*(y[C] - y[B]) - (y[B] - y[A])*(x[C] -x[B]))/2
x, y = {}, {}
n = int(raw_input())
for i in xrange(n):
  arr = raw_input().split()
  x[i] , y[i] = int(arr[0]), int(arr[1])

maxarea = 0
for i in xrange(n):
  for j in xrange(i+1, n):
    maxminus, maxplus = -1, -1
    for k in xrange(n):
      if k != i and k != j:
        a = area(i,j,k)
        if(a<0):
          maxminus = max(maxminus, -a)
        else:
          maxplus = max(maxplus, a)
    if maxplus >= 0 and maxminus >=0:
      maxarea = max(maxarea, (maxplus+maxminus))
print maxarea

The code is still giving me TLE on test case 7. Can anybody suggest further optimization?

\$\endgroup\$
1
\$\begingroup\$

You can do some minor optimization as follows:

def main():
    n = int(raw_input())
    coords = list([i] + map(int, raw_input().split()) for i in range(n))
    max_area = 0
    for a, Ax, Ay in coords:
        for b, Bx, By in coords[a+1:]:
            max_minus, max_plus = 0, -1
            for c, Cx, Cy in coords:
                if c != a and c != b:
                    ccw = (Bx - Ax) * (Cy - By) - (By - Ay) * (Cx - Bx)
                    if ccw < max_minus:
                        max_minus = ccw
                    elif ccw > max_plus:
                        max_plus = ccw
            if max_plus >= 0 and max_minus < 0 and max_plus - max_minus > max_area:
                max_area = max_plus - max_minus
    print(max_area / 2.0)

main()

Note that your use of float doesn't do anything because the values to be passed are integers. Anyway, there's no need to divide by 2 every time - you can just divide the final value by 2 at the end.

I think this still won't pass the speed test, though. If it is doable in python it probably needs an algorithm that makes better use of python's functions and standard library (and are other libraries allowed?). You could try something like this, for example:

from itertools import permutations
def main():
    n = int(raw_input())
    coords = list([i] + map(int, raw_input().split()) for i in range(n))
    max_area = 0
    for (a, Ax, Ay), (b, Bx, By) in permutations(coords, 2):
        ccws = [(Bx - Ax) * (Cy - By) - (By - Ay) * (Cx - Bx) 
                for c, Cx, Cy in coords if c != a and c != b] 
        low, high = min(ccws), max(ccws)
        if low < 0 and high >= 0 and high - low > max_area:
            max_area = high - low
    print(max_area / 2.0)
\$\endgroup\$
  • \$\begingroup\$ Coupled with the optimizations by @aseem-bansal above this reduced the time significantly for smaller test cases but it still fails on bigger test cases, I think the judge needs to update the time limit for Python in this problem. I have gone ahead and implemented the same program in Go and it passed without problems: codeforces.com/contest/340/submission/4391625 \$\endgroup\$ – Neerav Kumar Sep 1 '13 at 8:58
1
\$\begingroup\$

Firstly you need to put all the global statements into a function because of Python code runs faster in a function compared to global scope.

You don't need the arr variable. You can just use

x[i], y[i] = map(int, raw_input().split())

instead of using the two lines. map uses the function(1st argument) on each of the outputs from the second argument.

After placing the global statements into a function then instead of passing i, j, k you would need to pass the values directly.

I'll look up the algorithm and see if there are other changes that can be made.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.