DCEPC705 - Weird Points
Given N distinct points in a plane, a point (x1, y1) is said to be dominating another point (x2, y2) if x1>=x2 and y1>=y2.
The Dominance of a point is the absolute difference between 2 quantities – number of points dominated by this point and number of points not dominated by this point. (excluding itself)
A Weird point is the point whose Dominance value is greater than or equal to a threshold value ‘k’. Find the number of such Weird Points among those N given points.
Input
First line gives T, the number of test cases.
Each test case consists of 2 integers in first line, N and K, as specified above.
Next N lines give the coordinates of N points in the plane. “Xi” and “Yi” are space separated.
Output
Output T lines, each containing the required answer.
Constraints
1<=T<=10
1<=N<=10^5
1<=Xi, Yi<=10^9
0<=K<=N
Example
Input:
1 4 2 3 1
7 5
2 8
6 7 Output:
2
Problem Statement and Test Cases has been updated 2012-05-17 18:10:00.
hide comments
anonymous:
2023-02-18 17:06:15
There are test cases with coordinates out of given range: 1<=Xi, Yi<=10^9. |
|
depressedboy:
2022-01-21 15:34:00
Good problem .
|
|
yaseenmollik:
2020-03-25 19:01:13
Great Problem. Solved using BIT |
|
:D:
2012-05-17 16:14:12
Thanks for corrections! |
Added by: | dce coders |
Date: | 2012-04-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |
Resource: | Own Problem |