Click here to Skip to main content
15,867,838 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
Your competitive programming faculty decides to organize your lab which is near to all hostels. The students at University lives in n different hostels. The 2-d coordinates of hostels are given. Now, you want to help your faculty to decide the place for conducting lab which is near for all students. The distance between two points (a1,b1) and (a2,b2) is |a1−a2|+|b1−b2|, where |a| is the absolute value of a. You have to find the number of places (points with integer coordinates), so that the summary distance from all the hostels to the lab is minimal.

 

Input

First line contains a single integer t (1≤t≤1000)— the number of test cases.

The first line of each test case contains a single integer n (1≤n≤1000).

Next n lines describe the positions of the hostels (ai,bi) (0≤ai, bi≤109).

Ensure sum of all n does not exceed 1000.

 

Output

For each test case output a single integer - the number of different positions for the conduction of lab. The lab can be organized in the hostels also.

 

Sample Input

6

3

0 0

2 0

1 2

4

1 0        

0 2             

2 3

3 1

4

0 0   

0 1   

1 0

1 1

2

0 0

1 1

2

0 0

2 0

2

0 0

0 0

 

Sample Output

1

4

4

4

3

1


What I have tried:

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){    
    int n;
    cin>>n;
    vector<ll>x(n);
    vector<ll>y(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    if(n%2==1) cout<<1<<"\n";
    else{
        ll ans=(x[n/2]-x[n/2 - 1]+1)*(y[n/2]-y[n/2 -1]+1);
        cout<<ans<<"\n";
    }
}
    int main (){
    int t;
        cin>>t;
        for(int i=1;i<=t;i++){
           
        solve();
            
        }
        return 0;
    }
Posted
Updated 9-May-21 7:41am
v7
Comments
Patrice T 7-May-21 14:28pm    
Show your work.
Patrice T 7-May-21 14:56pm    
In "its length n is between 1 and 3⋅105, inclusive."
What was "3⋅105" in original requirement.
Dave Kreskowiak 9-May-21 12:18pm    
You can try to edit your question and remove all the details all you want. We'll just roll the question back to it's original form when you're done.

Quote:
can anyone do it

Yes.

But ... while we are more than willing to help those that are stuck: that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

And "Interview questions" are there to weed out those who can do the job from those who can't - and particularly to eliminate them before the expensive interview stage.
So our doing it for you teaches you nothing (as you learn by doing, not looking at the end result) and potentially deprives someone who can do the job from the opportunity to prove it t interview. As such, it really isn't fair on anyone: you, the other applicants, or the company hiring.
If you want to learn from this exercise and possibly start to grow into the position then you need to learn how to evaluate tasks like this, design, implement, document, and test a solution.
So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 
I get a better result than requirement sample:
302867235
032867235
023867235
023876235
023786235
023786325
023783625
023738625
023738652
023738562
023735862 // My best

Quote:
i failed

Show your work, we will tell you where you are wrong.
Quote:
but i think this question is helpful

Helpful to what ?
It is just a little logical game, should be solved in almost O(n).

[Update]
Looks like the problem is very popular.
A simple Google 3 0709 1337 246432
Give many answers, including sample code.
http://209.97.167.211/cfp.jsp?id=R1251C[^]
https://www.shuzhiduo.com/A/amd0wwN65g/[^]
The sample code look pretty complicated to me.
 
Share this answer
 
v2
Comments
Patrice T 9-May-21 0:58am    
And your code is ?
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){    
    int n;
    cin>>n;
    vector<ll>x(n);
    vector<ll>y(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    if(n%2==1) cout<<1<<"\n";
    else{
        ll ans=(x[n/2]-x[n/2 - 1]+1)*(y[n/2]-y[n/2 -1]+1);
        cout<<ans<<"\n";
    }
}
    int main (){
    int t;
        cin>>t;
        for(int i=1;i<=t;i++){
           
        solve();
            
        }
        return 0;
    }
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900