All Tracks Algorithms Sorting Quick Sort Problem

Earth and The Meteorites
Tag(s):

Easy, Sorting

Problem
Editorial
Analytics

Once upon a time, the Earth was a flat rectangular landmass. And there was no life. It was then that the sky lit up with meteorites falling from out of space. Wherever they fell on the planet, a river was born, which flowed in all 4 directions (North, East, West, South), till the waters reached the edge of the Earth and simply fell off into space.

Now, these rivers criss-crossed and divided the one huge landmass (Pangaea) into many smaller landmasses. Now the lifeless (there was no life, remember?), want to know the number of landmasses on the planet after all the meteorites have fallen. They also want to know the area of the smallest and largest landmass. Can you help the lifeless in this question?

Input:

First line contains T which is the number of test cases.

First line of every test case contains 3 integers N, M, Q where N and M are coordinates of the bottom right corner of the planet and Q is the number of meteorites.
The next Q lines contains the coordinates X, Y where each of the meteorites fell.

Output:

For each test case, output a line containing 3 integers indicating the number of regions, the minimum area and the maximum area.

Constraints:

  • 1 ≤ T ≤ 10
  • 2 ≤ N, M ≤ 105
  • 0 ≤ Q ≤ 105
  • 1 ≤ X ≤ N
  • 1 ≤ Y ≤ M
  • 0 ≤ sum of Q over all test cases ≤ 105

Scoring:

  • 2 ≤ N, M ≤ 10, 0 ≤ Q ≤ 10 : (30 pts)
  • 2 ≤ N, M ≤ 1000, 0 ≤ Q ≤ 1000 : (30 pts)
  • Original Constraints : (40 pts)

Note:

  • The Earth can be assumed to be a rectangle with top left point as (1,1) and bottom right point (N,M).
  • More than one meteorite may have landed at some point.
  • The rivers may be assumed to be flowing in very thin straight lines parallel to the edges of the planet.
SAMPLE INPUT
1
5 5 2
2 3
4 4

SAMPLE OUTPUT
9 1 4
Explanation

Refer to image below showing all the regions with individual areas.

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

IndiaHacks: Algorithms Qualifiers Round 2

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?