14,637,276 members
Rate this:
See more:
Chef has N axis-parallel rectangles in a 2D Cartesian coordinate system. These rectangles may intersect, but it is guaranteed that all their 4N vertices are pairwise distinct.

Unfortunately, Chef lost one vertex, and up until now, none of his fixes have worked (although putting an image of a point on a milk carton might not have been the greatest idea after all…). Therefore, he gave you the task of finding it! You are given the remaining 4N−1 points and you should find the missing one.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
Then, 4N−1 lines follow. Each of these lines contains two space-separated integers x and y denoting a vertex (x,y) of some rectangle.
Output
For each test case, print a single line containing two space-separated integers X and Y ― the coordinates of the missing point. It can be proved that the missing point can be determined uniquely.

Constraints
T≤100
1≤N≤2⋅105
|x|,|y|≤109
the sum of N over all test cases does not exceed 2⋅105

T=5
N≤20
Subtask #3 (50 points): original constraints

Example Input
1
2
1 1
1 2
4 6
2 1
9 6
9 3
4 3
Example Output
2 2
Explanation
The original set of points are:
fig1

Upon adding the missing point (2,2), N=2 rectangles can be formed:
fig1

What I have tried:

```#include <iostream>
using namespace std;
void quicksort(long int number[],long int n)
{
int i,j,a;
for (i = 0; i < n; ++i)
{

for (j = i + 1; j < n; ++j)
{

if (number[i] > number[j])
{

a =  number[i];
number[i] = number[j];
number[j] = a;

}

}
}
}
int main(void) {
long int n,i,j,k,rx,ry;
cin>>n;
for(i=0;i<n;i++)
{
cin>>k;
long int x[4*k-1],y[4*k-1];
for(j=0;j<4*k-1;j++)
{
cin>>x[j]>>y[j];
}
quicksort(x,4*k-1);
quicksort(y,4*k-1);
int flagx=0,flagy=0;
for(j=0;j<4*k-1;j=j+2)
{
if(!flagx||!flagy)
{
if(!flagx)
{
if(x[j]!=x[j+1])
{
rx=x[j];
flagx=1;
}}
if(!flagy)
{
if(y[j]!=y[j+1])
{
ry=y[j];
flagy=1;
}}
}
else
{break;}
}
cout<<rx<<" "<<ry<<endl;
}
return 0;
}```
Posted
Updated 12-Jul-20 5:47am
v10
Richard MacCutchan 12-Jul-20 6:33am

What is the question?
OriginalGriff 12-Jul-20 6:40am

"Can you write it for me?"
Just a guess ...
Richard MacCutchan 12-Jul-20 6:47am

Most likely.
sanskar srivastava 12-Jul-20 7:00am

Richard MacCutchan 12-Jul-20 7:20am

That is not a question.
sanskar srivastava 12-Jul-20 7:42am

you can visit and check the link please it's at the bottom.
Richard MacCutchan 12-Jul-20 7:44am

I have no intention of visiting any links. If you want help with your problem then please use the Improve question link above, and add the complete details.
sanskar srivastava 12-Jul-20 9:47am

okay, the whole question is here with a sample input-output
Patrice T 12-Jul-20 7:59am

Your code was corrupted when copied.
sanskar srivastava 12-Jul-20 9:48am

thanks for the help.
Rick York 12-Jul-20 14:06pm

One recommendation : learn how to read data from a file so you don't have to enter your data by hand every single time. This will give you much more time to debug your code and make it run correctly.

Rate this:

## Solution 1

Quote:
Code chef problem solved but need to optimise due to TLE .

As usual, CodeChef challenges are challenges, this means that straightforward programs are never the solution.
If N is 200000 rectangles, there is 799999 points.
Your code is matching points as 79.9999*79.9999=639.998.400.001 checks for x and as much for y.
The key is in Data Structures and Algorithms. Some data structures and algorithms allow to get faster, but learning them is a learning of a life, there is always something interesting to learn.

Example of simple optimization, but I fear is not enough :
Dividing the search by 4: for any x[j] matched with an x[i], swap (x[j+1], x[i]) and don't search x[j+1]. The swap makes that any previous x[j] is matched with x[j+1], so there is no need to search x[j+1], divide by 2. This imply that for any x[j], there is no search to do on any x[i] for 0 <= i <= j, divide by 2 again.
-----
Advice: Learn to indent properly your code, it show its structure and it helps reading and understanding. It also helps spotting structures mistakes.
```#include <iostream>
using namespace std;
void quicksort(long int number[],long int n)
{
int i,j,a;
for (i = 0; i < n; ++i)
{

for (j = i + 1; j < n; ++j)
{

if (number[i] > number[j])
{

a =  number[i];
number[i] = number[j];
number[j] = a;

}

}
}
}
int main(void) {
long int n,i,j,k,rx,ry;
cin>>n;
for(i=0;i<n;i++)
{
cin>>k;
long int x[4*k-1],y[4*k-1];
for(j=0;j<4*k-1;j++)
{
cin>>x[j]>>y[j];
}
quicksort(x,4*k-1);
quicksort(y,4*k-1);
int flagx=0,flagy=0;
for(j=0;j<4*k-1;j=j+2)
{
if(!flagx||!flagy)
{
if(!flagx)
{
if(x[j]!=x[j+1])
{
rx=x[j];
flagx=1;
}
}
if(!flagy)
{
if(y[j]!=y[j+1])
{
ry=y[j];
flagy=1;
}
}
}
else
{
break;
}
}
cout<<rx<<" "<<ry<<endl;
}
return 0;
}```

Indentation style - Wikipedia[^]

Professional programmer's editors have this feature and others ones such as parenthesis matching and syntax highlighting.
ultraedit[^]
-----
[Update]
I fear your quicksort routine is not a quicksort algorithm, it is more a bubble sort.
The changes I proposed are O(N²/4)
Using a balanced binary tree can lead to something like O(N*log(N))
Self-balancing binary search tree - Wikipedia[^]
Red–black tree - Wikipedia[^]
v9