c++ Source Code for acm 2004-2005 problems

Gabriel Genellina gagsl-py2 at yahoo.com.ar
Mon Jul 13 01:13:43 CEST 2009


En Sun, 12 Jul 2009 19:24:57 -0300, Davood Vahdati  
<davoodvahdati2009 at gmail.com> escribió:

> it is an Acm programming competition Questions in year 2004-2005 .
> could you please solve problems is question ? I  Wan't C++ Source Code
> program About this questions OR Problems . thank you for your prompt
> attention to this matter

Not C++ code but Python: A brute force approach to the first problem.

> Parallelogram Counting
> There are n distinct points in the plane, given by their integer
> coordinates. Find the number of parallelograms whose
> vertices lie on these points.

class Point:
   def __init__(self, x, y): self.x, self.y = x, y
   def __repr__(self): return 'Point(%d,%d)' % (self.x, self.y)

class Segment:
   def __init__(self, p0, p1): self.p0, self.p1 = p0, p1
   def is_parallel(self, other):
     return ((self.p1.x-self.p0.x) * (other.p1.y-other.p0.y) -
             (self.p1.y-self.p0.y) * (other.p1.x-other.p0.x) == 0)

points = [
     Point(-2,-1),
     Point(8,9),
     Point(5,7),
     Point(1,1),
     Point(4,8),
     Point(2,0),
     Point(9,8)]

n = 0
for i,A in enumerate(points):
   for B in points[i+1:]:
     AB = Segment(A,B)
     for C in points:
       if C in (A,B): continue
       BC = Segment(B,C)
       for D in points:
         if D in (A,B,C): continue
         CD = Segment(C,D)
         if AB.is_parallel(CD) and BC.is_parallel(Segment(A,D)):
           print A,B,C,D
           n += 1

n /= 4 # ABCD,BCDA,CDAB,DABC ## BACD etc already removed
print n

-- 
Gabriel Genellina




More information about the Python-list mailing list