Given a set of n points (xi, yi) in 2D coordinate. Each point has some weight wi. The task is to check whether a line at 45 degrees can be drawn so that sum of weights of points on each side is equal.
Examples:
Input : x1 = -1, y1 = 1, w1 = 3 x2 = -2, y2 = 1, w2 = 1 x3 = 1, y3 = -1, w3 = 4 Output : Yes
Input : x1 = 1, y1 = 1, w1 = 2 x2 = -1, y2 = 1, w2 = 1 x3 = 1, y3 = -1, w3 = 2 Output : No
First, let’s try to solve the above problem for a vertical line i.e if a line x = i can divide the plane into two-part such that the sum of weight at each side is equal.
Observe, multiple points with the same x-coordinate can be treated as one point with a weight equal to the sum of weights of all points with the same x-coordinate.
Now, traverse through all x-coordinates from the minimum x-coordinate to maximum x-coordinate. So, make an array prefix_sum[], which will store the sum of weights till the point x = i.
So, there can be two options for which the answer can be ‘Yes’:
- Either prefix_sum[1, 2, …, i-1] = prefix_sum[i+1, …, n]
- or there exist a point i such that a line passes somewhere in between
x = i and x = i+1 and prefix_sum[1, …, i] = prefix_sum[i+1, …, n],
where prefix_sum[i, …, j] is the sum of weight of points from i to j.
int is_possible = false;
for (int i = 1; i < prefix_sum.size(); i++)
if (prefix_sum[i] == total_sum - prefix_sum[i])
is_possible = true
if (prefix_sum[i-1] == total_sum - prefix_sum[i])
is_possible = true
Now, to solve for a line at 45 degrees, we will rotate each point by 45 degrees.
Refer: 2D Transformation or Rotation of objects
So, point at (x, y), after 45 degree rotation will become ((x – y)/sqrt(2), (x + y)/sqrt(2)).
We can ignore the sqrt(2) since it is the scaling factor. Also, we don’t need to care about y-coordinate after rotation because a vertical line cannot distinguish between the point having the same x-coordinate. (x, y1) and (x, y2) will lie to the right, left or on any line of the form x = k.
C++
#include <bits/stdc++.h>using namespace std;// Checking if a plane can be divide by a line// at 45 degrees such that weight sum is equalvoid is_partition_possible(int n, int x[], int y[], int w[]){ map<int, int> weight_at_x; int max_x = -2e3, min_x = 2e3; // Rotating each point by 45 degrees and // calculating prefix sum. // Also, finding maximum and minimum x // coordinates for (int i = 0; i < n; i++) { int new_x = x[i] - y[i]; max_x = max(max_x, new_x); min_x = min(min_x, new_x); // storing weight sum upto x - y point weight_at_x[new_x] += w[i]; } vector<int> sum_till; sum_till.push_back(0); // Finding prefix sum for (int x = min_x; x <= max_x; x++) { sum_till.push_back(sum_till.back() + weight_at_x[x]); } int total_sum = sum_till.back(); int partition_possible = false; for (int i = 1; i < sum_till.size(); i++) { if (sum_till[i] == total_sum - sum_till[i]) partition_possible = true; // Line passes through i, so it neither // falls left nor right. if (sum_till[i - 1] == total_sum - sum_till[i]) partition_possible = true; } printf(partition_possible ? "YES\n" : "NO\n");}// Driven Programint main(){ int n = 3; int x[] = { -1, -2, 1 }; int y[] = { 1, 1, -1 }; int w[] = { 3, 1, 4 }; is_partition_possible(n, x, y, w); return 0;} |
Java
import java.util.*;// Checking if a plane can be divide by a line // at 45 degrees such that weight sum is equalclass GFG {static void is_partition_possible(int n, int x[], int y[], int w[]) { Map<Integer, Integer> weight_at_x = new HashMap<Integer, Integer>(); int max_x = (int) -2e3, min_x = (int) 2e3; // Rotating each point by 45 degrees and // calculating prefix sum. // Also, finding maximum and minimum x // coordinates for (int i = 0; i < n; i++) { int new_x = x[i] - y[i]; max_x = Math.max(max_x, new_x); min_x = Math.min(min_x, new_x); // storing weight sum upto x - y point if(weight_at_x.containsKey(new_x)) { weight_at_x.put(new_x, weight_at_x.get(new_x) + w[i]); } else { weight_at_x.put(new_x,w[i]); } //weight_at_x[new_x] += w[i]; } Vector<Integer> sum_till = new Vector<>(); sum_till.add(0); // Finding prefix sum for (int s = min_x; s <= max_x; s++) { if(weight_at_x.get(s) == null) sum_till.add(sum_till.lastElement()); else sum_till.add(sum_till.lastElement() + weight_at_x.get(s)); } int total_sum = sum_till.lastElement(); int partition_possible = 0; for (int i = 1; i < sum_till.size(); i++) { if (sum_till.get(i) == total_sum - sum_till.get(i)) partition_possible = 1; // Line passes through i, so it neither // falls left nor right. if (sum_till.get(i-1) == total_sum - sum_till.get(i)) partition_possible = 1; } System.out.printf(partition_possible == 1 ? "YES\n" : "NO\n"); } // Driven code public static void main(String[] args) { int n = 3; int x[] = { -1, -2, 1 }; int y[] = { 1, 1, -1 }; int w[] = { 3, 1, 4 }; is_partition_possible(n, x, y, w); }}/* This code contributed by PrinciRaj1992 */ |
Python3
from collections import defaultdict# Checking if a plane can be divide by a line# at 45 degrees such that weight sum is equaldef is_partition_possible(n, x, y, w): weight_at_x = defaultdict(int) max_x = -2e3 min_x = 2e3 # Rotating each point by 45 degrees and # calculating prefix sum. # Also, finding maximum and minimum x # coordinates for i in range(n): new_x = x[i] - y[i] max_x = max(max_x, new_x) min_x = min(min_x, new_x) # storing weight sum upto x - y point weight_at_x[new_x] += w[i] sum_till = [] sum_till.append(0) # Finding prefix sum for x in range(min_x, max_x + 1): sum_till.append(sum_till[-1] + weight_at_x[x]) total_sum = sum_till[-1] partition_possible = False for i in range(1, len(sum_till)): if (sum_till[i] == total_sum - sum_till[i]): partition_possible = True # Line passes through i, so it neither # falls left nor right. if (sum_till[i - 1] == total_sum - sum_till[i]): partition_possible = True if partition_possible: print("YES") else: print("NO")# Driven Programif __name__ == "__main__": n = 3 x = [-1, -2, 1] y = [1, 1, -1] w = [3, 1, 4] is_partition_possible(n, x, y, w) # This code is contributed by chitranayal. |
C#
// Checking if a plane can be divide by a line // at 45 degrees such that weight sum is equalusing System;using System.Collections.Generic;public class GFG{ static void is_partition_possible(int n, int[] x, int[] y, int[] w) { Dictionary<int,int> weight_at_x = new Dictionary<int,int>(); int max_x = (int) -2e3, min_x = (int) 2e3; // Rotating each point by 45 degrees and // calculating prefix sum. // Also, finding maximum and minimum x // coordinates for (int i = 0; i < n; i++) { int new_x = x[i] - y[i]; max_x = Math.Max(max_x, new_x); min_x = Math.Min(min_x, new_x); // storing weight sum upto x - y point if(weight_at_x.ContainsKey(new_x)) { weight_at_x[new_x]+=w[i]; } else { weight_at_x.Add(new_x,w[i]); } // weight_at_x[new_x] += w[i]; } List<int> sum_till = new List<int>(); sum_till.Add(0); // Finding prefix sum for (int s = min_x; s <= max_x; s++) { if(!weight_at_x.ContainsKey(s)) { sum_till.Add(sum_till[sum_till.Count - 1]); } else { sum_till.Add(sum_till[sum_till.Count-1] + weight_at_x[s]); } } int total_sum = sum_till[sum_till.Count-1]; int partition_possible = 0; for (int i = 1; i < sum_till.Count; i++) { if (sum_till[i] == total_sum - sum_till[i]) partition_possible = 1; // Line passes through i, so it neither // falls left nor right. if (sum_till[i-1] == total_sum - sum_till[i]) partition_possible = 1; } Console.WriteLine(partition_possible == 1 ? "YES" : "NO"); } // Driven code static public void Main (){ int n = 3; int[] x = { -1, -2, 1 }; int[] y = { 1, 1, -1 }; int[] w = { 3, 1, 4 }; is_partition_possible(n, x, y, w); }}// This code is contributed by rag2127 |
Javascript
<script>// Checking if a plane can be divide by a line// at 45 degrees such that weight sum is equal function is_partition_possible(n,x,y,w) { let weight_at_x = new Map(); let max_x = -2e3, min_x = 2e3; // Rotating each point by 45 degrees and // calculating prefix sum. // Also, finding maximum and minimum x // coordinates for (let i = 0; i < n; i++) { let new_x = x[i] - y[i]; max_x = Math.max(max_x, new_x); min_x = Math.min(min_x, new_x); // storing weight sum upto x - y point if(weight_at_x.has(new_x)) { weight_at_x.set(new_x, weight_at_x.get(new_x) + w[i]); } else { weight_at_x.set(new_x,w[i]); } //weight_at_x[new_x] += w[i]; } let sum_till = []; sum_till.push(0); // Finding prefix sum for (let s = min_x; s <= max_x; s++) { if(weight_at_x.get(s) == null) sum_till.push(sum_till[sum_till.length-1]); else sum_till.push(sum_till[sum_till.length-1] + weight_at_x.get(s)); } let total_sum = sum_till[sum_till.length-1]; let partition_possible = 0; for (let i = 1; i < sum_till.length; i++) { if (sum_till[i] == total_sum - sum_till[i]) partition_possible = 1; // Line passes through i, so it neither // falls left nor right. if (sum_till[i-1] == total_sum - sum_till[i]) partition_possible = 1; } document.write(partition_possible == 1 ? "YES\n" : "NO\n"); } // Driven code let n = 3; let x=[ -1, -2, 1 ]; let y=[1, 1, -1 ]; let w=[ 3, 1, 4 ]; is_partition_possible(n, x, y, w); // This code is contributed by avanitrachhadiya2155</script> |
Output:
Yes
Time Complexity: O(nlogn + max) where max = 4*103
Auxiliary Space: O(n + max)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
