Tutorialspoint.dev

Minimum number of points to be removed to get remaining points on one side of axis

We are given n points in a Cartesian plane. Our task is to find the minimum number of points that should be removed in order to get the remaining points on one side of any axis.

Examples :

Input : 4
        1 1
        2 2
       -1 -1
       -2 2
Output : 1
Explanation :
If we remove (-1, -1) then all the remaining 
points are above x-axis. Thus the answer is 1.

Input : 3
        1 10
        2 3
        4 11
Output : 0
Explanation :
All points are already above X-axis. Hence the
answer is 0.  



Approach :
This problem is a simple example of constructive brute force algorithm on Geometry. The solution can be approached simply by finding the number of points on all sides of the X-axis and Y-axis. The minimum of this will be the answer.

C++

// CPP program to find minimum points to be moved
// so that all points are on same side.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
  
// Structure to store the coordinates of a point.
struct Point 
{
    int x, y;
};
  
// Function to find the minimum number of points
int findmin(Point p[], int n)
{
    int a = 0, b = 0, c = 0, d = 0;
    for (int i = 0; i < n; i++) 
    {
        // Number of points on the left of Y-axis.
        if (p[i].x <= 0)         
            a++;
  
        // Number of points on the right of Y-axis.
        else if (p[i].x >= 0) 
            b++;
  
        // Number of points above X-axis.
        if (p[i].y >= 0) 
            c++;
  
        // Number of points below X-axis.
        else if (p[i].y <= 0) 
            d++;
    }
  
    return min({a, b, c, d});
}
  
// Driver Function
int main()
{
    Point p[] = { {1, 1}, {2, 2}, {-1, -1}, {-2, 2} };
    int n = sizeof(p)/sizeof(p[0]);
    cout << findmin(p, n);
    return 0;
}

Python3

# Python3 program to find minimum points to be
# moved so that all points are on same side.

# Function to find the minimum number
# of points
def findmin(p, n):

a, b, c, d = 0, 0, 0, 0
for i in range(n):

# Number of points on the left
# of Y-axis.
if (p[i][0] <= 0): a += 1 # Number of points on the right # of Y-axis. elif (p[i][0] >= 0):
b += 1

# Number of points above X-axis.
if (p[i][1] >= 0):
c += 1

# Number of points below X-axis.
elif (p[i][1] <= 0): d += 1 return min([a, b, c, d]) # Driver Code p = [ [1, 1], [2, 2], [-1, -1], [-2, 2] ] n = len(p) print(findmin(p, n)) # This code is contributed by Mohit Kumar [tabbyending] Output :

1


This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter