Points and Lines codechef
Points and Lines codechef Question:-
Given N points of the form (xi,yi) on a 2-D plane.
From each point, you draw 22 lines one horizontal and one vertical. Now some of the lines may overlap each other, therefore you are required to print the number of distinct lines you can see on the plane.
Note:
- Two horizontal lines are distinct if they pass through different yy coordinates.
- Two vertical lines are distinct if they pass through different xx coordinates.
Input Format
- First line will contain TT, number of testcases. Then the testcases follow.
- Each testcase contains a single integer NN, the number of points.
- The next NN lines contain two space separated integers xi,yixi,yi, the coordinate of the ithith point.
Output Format
For each testcase, output in a single line the number of distinct lines that can be seen on the plane.
Constraints
- 1≤T≤10001≤T≤1000
- 1≤N≤1051≤N≤105
- 0≤Xi,Yi≤1090≤Xi,Yi≤109
- Sum of NN over all test cases is atmost 105105.
Sample Input 1
3
4
1 1
1 0
0 1
0 0
5
0 0
0 1
0 2
0 3
0 4
1
10 10
Sample Output 1
4
6
2
Explanation
Test Case 11: There are 22 horizontal lines passing through Y=0Y=0 and Y=1Y=1, and 22 vertical lines passing through X=0X=0 and X=1X=1.
Test Case 22: There are 55 horizontal lines passing through Y=0,Y=1,Y=2,Y=3Y=0,Y=1,Y=2,Y=3 and Y=4Y=4 and 11 vertical line passing through X=0X=0.
Test Case 33: There is 11 horizontal line passing through Y=10Y=10 and 11 vertical line passing through X=10X=10.
Code of Points and Lines codechef:-
t=int(input()) for j in range(t): h=[] v=[] ans=0 n=int(input()) for i in range(n): e=input().split() h.append(e[0]) v.append(e[1]) if e[0]==1 and e[1]==0: ans+=1 h=list(set(h)) v=list(set(v)) ans=ans+len(h)+len(v) print(ans)
Points and Lines codechef
Recommended post:-
- c program to convert specified days into years weeks and days
- Print Reverse Hollow Pyramid
- Update the booking ID | Wipro previous year question paper
- Pages in PDF | Wipro previous year question paper
- Sparse Matrix in data structure
- Find the location ID | Wipro previous year Coding question
- find the odd digits | Wipro Coding question
- Find the product id | Wipro Coding question
- Difference between static and dynamic memory allocation
- What is asymptotic Notation