Problem B:
My idea is to have a set(can be implemented using STL's std::set) with
key being a pair (dx,dy).
now, i go through all pairs of points, and i construct the key(x_1-
x_0,y_1,y_0) for them. The idea is that if i have L pairs each with
the same (dx,dy), every two pairs make a parallelogram. And so, after
putting them all inside, i go through the set and say that if I have L
pairs with the same (dx,dy), i add L*(L-1)/2 to a counter, and in the
end i divide by 2, since i counted each parallelogram twice.
Now, this is not accurate, because this way i count 4 points on a
straight line as a parallelogram. So, instead of just counting how
many pairs are with this (dx,dy), i count how many different lines are
with this slope. that is, for a specific slope, (dx,dy), i maintain a
second level set that contains the intersections with the y axis, and
in the end, i use inclusion exclusion on each slope, and i end up with
a (N log N) algorithm.
Sincerely,
Shahar Papini
On Jul 8, 11:58 am, Davood Vahdati <davoodvahdati2...@gmail.com>
wrote:
> it is an Acm programming competition Questions in year 2004-2005 . could you
> please solve problems is question ? thank you .
>
> 29th ACM International Collegiate
>
> Sponsored by
>
> Programming Contest, 2004-2005
> Sharif Preliminary Contest
> Sharif University of Technology, 28 Oct. 2004
>
> Problem B
> (Program filename: B.CPP, B.DPR, B.PAS or B.java)
>
> 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. In other words, find the number of 4-element
> subsets of these points that can be written as
> {A, B, C, D} such that AB || CD, and BC || AD. No four points are in a
> straight line.
>
> Input (filename: B.IN)
>
> The first line of the input file contains a single integer t (1 £ t £ 10),
> the number of test cases. It is followed by the input
>
> data for each test case.
> The first line of each test case contains an integer n (1 £ n £ 1000). Each
> of the next n lines, contains 2 space-separated
> integers x and y (the coordinates of a point) with magnitude (absolute
> value) of no more than 1000000000.
>
> Output (Standard Output)
>
> Output should contain t lines.
> Line i contains an integer showing the number of the parallelograms as
> described above for test case i.
>
> Sample Input
>
> 2
> 6
> 0 0
> 2 0
> 4 0
> 1 1
> 3 1
> 5 1
> 7
> -2 -1
> 8 9
> 5 7
> 1 1
> 4 8
> 2 0
> 9 8
>
> Sample Output
>
> 5
> 6
>
> ----------------------------------------------------------------------------------------------------------------------
> Problem B-Page 1 of 1
>
> 28th ACM International Collegiate
>
> Sponsored by
>
> Programming Contest, 2003-2004
> Sharif Preliminary Contest
> Sharif University of Technology, 14 Nov. 2003
>
> Problem C
> (Program filename: C.CPP or C.PAS or C.DPR or C.java)
>
> Toy Storage
>
> Mom and dad have a problem: their child, Reza, never puts his toys away when
> he is finished playing with them.
> They gave Reza a rectangular box to put his toys in. Unfortunately, Reza is
> rebellious and obeys his parents by simply
> throwing his toys into the box. All the toys get mixed up, and it is
> impossible for Reza to find his favorite toys anymore.
>
> Reza's parents came up with the following idea. They put cardboard
> partitions into the box. Even if Reza keeps
> throwing his toys into the box, at least toys that get thrown into different
> partitions stay separate. The box looks like this
> from the top:
>
> We want for each positive integer t, such that there exists a partition with
> t toys, determine how many partitions
> have t, toys.
>
> Input (filename: C.IN)
>
> The input consists of a number of cases. The first line consists of six
> integers n, m, x1, y1, x2, y2. The number of
> cardboards to form the partitions is n (0< n £ 1000) and the number of toys
> is given in m (0<m £ 1000). The
> coordinates of the upper-left corner and the lower-right corner of the box
> are (x1, y1) and (x2, y2), respectively. The
> following n lines each consists of two integers Ui Li, indicating that the
> ends of the ith cardboard is at the coordinates
> (Ui, y1) and (Li, y2). You may assume that the cardboards do not intersect
> with each other. The next m lines each consists
> of two integers Xi Yi specifying where the ith toy has landed in the box.
> You may assume that no toy will land on a
> cardboard.
> A line consisting of a single 0 terminates the input.
>
> Output (filename: C.OUT)
>
> For each box, first provide a header stating “Box”
> on a line of its own. After that, there will be one line of output per
> count (t> 0) of toys in a partition. The value t will be followed by a colon
> and a space, followed the number of
>
> partitions containing t toys. Output will be sorted in ascending order of t
> for each box.
>
> Sample Input
>
> 4 10 0 10 100 0
> 20 20
> 80 80
> 60 60
> 40 40
> 5 10
> 15 10
> 95 10
> 25 10
> 65 10
> 75 10
> 35 10
> 45 10
> 55 10
> 85 10
> 5 6 0 10 60 0
>
> 4 3
> 15 30
> 3 1
> 6 8
> 10 10
> 2 1
> 2 8
> 1 5
> 5 5
> 40 10
> 7 9
> 0
>
> Sample Output
>
> Box
>
> 2: 5
> Box
> 1: 4
> 2: 1
> ----------------------------------------------------------------------
> 29th ACM International Collegiate
> Sponsored by
> Programming Contest, 2004-2005
> Sharif Preliminary Contest
> Sharif University of Technology, 28 Oct. 2004
>
> Problem D
> (Program filename: D.CPP, D.DPR, or D.java)
>
> Software Company
> A software developing company has been assigned two programming projects. As
>
> both projects are within the same contract, both must be handed in at the
> same
> time. It does not help if one is finished earlier.
>
> This company has n employees to do the jobs. To manage the two projects more
>
> easily, each is divided into m independent subprojects. Only one employee
> can
> work on a single subproject at one time, but it is possible for two
> employees to
> work on different subprojects of the same project simultaneously.
>
> Our goal is to finish the projects as soon as possible.
>
> Input (filename: D.IN)
> The first line of the input file contains a single integer t (1 £ t £ 11),
> the
> number of test cases, followed by the input data for each test case. The
> first
> line of each test case contains two integers n (1 £ n £ 100), and m (1 £ m £
>
> 100). The input for this test case will be followed by n lines. Each line
> contains two integers which specify how much time in seconds it will take
> for
> the specified employee to complete one subproject of each project. So if the
>
> line contains x and y, it means that it takes the employee x seconds to
> complete
> a subproject from the first project, and y seconds to complete a subproject
> from
> the second project.
> Output (Standard Output)
> There should be one line per test case containing the minimum amount of time
> in
> seconds after which both projects can be completed.
>
> Sample Input
> 1
> 3 20
> 1 1
> 2 4
> 1 6
>
> Sample Output
> 18
>
> Problem D -Page 1 of 1
>
> 29th ACM International Collegiate
> Sponsored by
> Programming Contest, 2004-2005
> Sharif Preliminary Contest
> Sharif University of Technology, 28 Oct. 2004
> ----------------------------------------------------------------------
> Problem F
> (Program filename: F.CPP, F.DPR, or F.java)
>
> Median Weight Bead
> There are N beads which of the same shape and size, but with different
> weights.
> N is an odd number and the beads are labeled as 1, 2, ..., N. Your task is
> to
> find the bead whose weight is median (the ((N+1)/2)th among all beads). The
> following comparison has been performed on some pairs of beads:
> A scale is given to compare the weights of beads. We can determine which one
> is
> heavier than the other between two beads. As the result, we now know that
> some
> beads are heavier than others. We are going to remove some beads which
> cannot
> have the medium weight.
>
> For example, the following results show which bead is heavier after M
> comparisons where M=4 and N=5.
>
> 1. Bead 2 is heavier than Bead 1.
> 2. Bead 4 is heavier than Bead 3.
> 3. Bead 5 is heavier than Bead 1.
> 4. Bead 4 is heavier than Bead 2.
> From the above results, though we cannot determine exactly which is the
> median
> bead, we know that Bead 1 and Bead 4 can never have the median weight: Beads
> 2,
> 4, 5 are heavier than Bead 1, and Beads 1, 2, 3 are lighter than Bead 4.
> Therefore, we can remove these two beads.
> Write a program to count the number of beads which cannot have the median
> weight.
>
> Input (filename: F.IN)
> The first line of the input file contains a single integer t (1 £ t £ 11),
> the
> number of test cases, followed by the input data for each test case. The
> input
> for each test case will be as follows:
> The first line of input data contains an integer N (1=N=99) denoting the
> number
> of beads, and M denoting the number of pairs of beads compared. In each of
> the
> next M lines, two numbers are given where the first bead is heavier than the
>
> second bead.
> Output (Standard Output)
> There should be one line per test case. Print the number of beads which can
> never have the medium weight.
>
> Sample Input Sample Output
> 1 2
> 5 4
> 2 1
> 4 3
> 5 1
> 4 2
> Problem F -Page 1 of 2
>
> ACM.rar
> 63KViewDownload
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
