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