# Is any further optimization possible? (Codeforces)

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?

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)

• 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 – Neerav Kumar Sep 1 '13 at 8:58

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.