Click here to Skip to main content
14,637,276 members
Rate this:
Please Sign up or sign in to vote.
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:

#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.
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.

1 solution

Rate this:
Please Sign up or sign in to vote.

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.
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.
#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[^]
   
v9

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




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100