Dado un conjunto de n puntos (x i , y i ) en coordenadas 2D. Cada punto tiene un peso w i . La tarea es verificar si se puede dibujar una línea a 45 grados para que la suma de los pesos de los puntos en cada lado sea igual.
Ejemplos:
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
Primero, intentemos resolver el problema anterior para una línea vertical, es decir, si una línea x = i puede dividir el plano en dos partes, de modo que la suma del peso en cada lado sea igual.
Observe que varios puntos con la misma coordenada x se pueden tratar como un punto con un peso igual a la suma de los pesos de todos los puntos con la misma coordenada x.
Ahora, recorra todas las coordenadas x desde la coordenada x mínima hasta la coordenada x máxima. Por lo tanto, cree una array prefix_sum[] , que almacenará la suma de los pesos hasta el punto x = i .
Entonces, puede haber dos opciones para las cuales la respuesta puede ser ‘Sí’:
- Prefix_sum[1, 2, …, i-1] = prefix_sum[i+1, …, n]
- o existe un punto i tal que una línea pasa en algún lugar entre
x = i y x = i+1 y suma_prefijo[1, …, i] = suma_prefijo[i+1, …, n],
donde suma_prefijo[i, … , j] es la suma de los pesos de los puntos de i a 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
Ahora, para resolver una línea a 45 grados, rotaremos cada punto 45 grados.
Consulte: Transformación 2D o Rotación de objetos
Entonces, apunte a (x, y), después de una rotación de 45 grados se convertirá en ((x – y)/sqrt(2), (x + y)/sqrt(2)).
Podemos ignorar el sqrt(2) ya que es el factor de escala. Además, no necesitamos preocuparnos por la coordenada y después de la rotación porque una línea vertical no puede distinguir entre el punto que tiene la misma coordenada x. (x, y 1 ) y (x, y 2 ) estarán a la derecha, a la izquierda o en cualquier línea de la forma 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 equal
void 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 Program
int 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 equal
class 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 equal
def 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 Program
if __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 equal
using 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>
Producción:
Yes
Complejidad de tiempo : O(nlogn + max) donde max = 4*10 3
Espacio auxiliar : O(n + max)