Balanced Partition
Practice
4.7 (35 votes)
Algorithms
Bubble sort algorithm
Easy
Rotation
Sorting
Rotations
Problem
86% Success 4780 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

There are \(n \) houses in the village Dholakpur. The location of each house in the village can be given as \((x_i, y_i)\) in the Cartesian coordinate plane. There are \(h_i\) persons living in the \(i^{th}\) house. Central electricity authority of the village is set to built a wire line across the village. The wire line is supposed to constructed in a way such that it is the north-east direction. In other words the wire line is parallel to the line \(y = x\). Given that the construction of such line is considered to be effective only if the number of persons living in its left and right side are equal, can you tell if the construction of such wire line is possible? 

Note: If the wire line passes through any house, the house is not considered in either half.

Constraints:

  • \(1 \le t \le 100 \)
  • \(2 \le n \le 2 \times 10^3\)
  • \(-10^3 \le x_i, y_i \le 10^3\)
  • \(1 \le h_i \le 10^3\)
  • It is guaranteed that no two houses are at the same location.

Input Format:

The first line contains a single integer \(t\)  denoting the number of test cases.

The first line of each test case contains \(n\)  i.e the number houses in the village. Next \(n\) lines contains \(3\) space-separated integers \(x_i, y_i \text{ and } h_i\)

Output Format:

Print \(t\)  lines each containing a "YES" or "NO" (without quotes). \(i^{th}\) line corresponds to the answer of the \(i^{th}\) testcase.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
81 votes
Tags:
ApprovedEasySortingTwo pointer