Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `flowin.txt`

**Output File:** `flowout.txt`

**Time Limit:** 0.2 second

You run a florist in central Oklahoma where the land is bare and nothing grows. In an effort to boost your sagging sales, you decide to experiment with different types of fertiliser.

You take a square patch of land and divide it into four quarters. The quarters are numbered from 1 to 4 as shown below. In each quarter you use a different type of fertiliser, and throughout the spring you record where the flowers grow.

1 | 2 |

3 | 4 |

At the end of spring you have a long list of coordinates, each pair of coordinates representing a flower that appeared. Your task is to determine which fertiliser produced the most flowers.

The first line of the input file will contain the single integer
*N* representing the size of each quadrant
(1 <= *N* <= 1,000).
The second line will contain the single integer *M* representing the
total number of flowers whose coordinates
you recorded
(1 <= *M* <= 100,000).

Following this will be *M* lines, each representing a single flower. Each
of these lines will be of the form *x y*, where *x* and
*y* are the
integer x- and y-coordinates at which the flower grew
(1 <= *x*,*y* <= 2*N*).

The diagram below shows how the coordinates are located on the patch of land.
Quarters 1 and 3 have *x* coordinates from 1 to *N*
inclusive; quarters 2 and 4 have *x* coordinates from
*N*+1 to 2*N* inclusive.
Quarters 1 and 2 have *y* coordinates from 1 to *N*
inclusive; quarters 3 and 4 have *y* coordinates from *N*+1 to
2*N* inclusive.

Note that over the course of spring, many different flowers might appear at the same location.

The output must be a single line of the form *q f*, where
*q* is the
quarter that produced the most flowers and *f* is the number of
flowers that this quarter produced. You may assume that there is
always a single quarter with the most flowers.

3 7 2 2 6 2 2 5 2 3 6 5 1 3 5 6

1 3

The scenario above represents the following plot of land. In this case the best quarter is quarter 1 which produced 3 flowers.

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:10am AEDT