Click here to Skip to main content
15,886,362 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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
Subtasks
Subtask #1 (20 points):

T=5
N≤20
Subtask #2 (30 points): |x|,|y|≤105
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:

C++
#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) {
	// your code goes here
	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
Comments
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    
added the link of the question go and check please
Richard MacCutchan 12-Jul-20 7:20am    
That is not a question.

1 solution

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.
Your code is in O(n²).
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.
C++
#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) {
    // your code goes here
    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.
Notepad++ Home[^]
ultraedit[^]
-----
[Update]
I fear your quicksort routine is not a quicksort algorithm, it is more a bubble sort.
Your first code was O(n²)
Your new code is O(N²/2)
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[^]
 
Share this answer
 
v9

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