Considere n puntos en el plano de coordenadas cartesianas. Deje que el punto (X i , Y i ) tenga un valor V i . Se dice que una recta paralela al eje y es una buena recta de partición si la suma de los valores de los puntos de su izquierda es igual a la suma de los valores de los puntos de su derecha. Tenga en cuenta que si un punto se encuentra en la línea de partición, no se considera en ningún lado de la línea. La tarea es imprimir Sí si existe una buena línea de partición; de lo contrario, imprimir No.
Ejemplo:
Entrada: X[] = {-3, 5, 8}, Y[] = {8, 7, 9}, V[] = {8, 2, 10}
Salida: Sí
x = c donde 5 < c < 8 es una buena
línea de partición ya que la suma de los valores en ambos lados es 10.
Entrada: X[] = {-2, 5, 8, 9}, Y[] = {7, 7, 9, 8}, V[] = {6, 2, 1, 8}
Salida: Sí
Acercarse:
- Cuente el valor en cada coordenada x. Esto significa que si hay varios puntos con la misma coordenada x, se tratarán como un solo punto y se sumarán sus valores.
- Comience desde la coordenada x mínima y verifique si una de las siguientes condiciones se cumple en X i :
- La suma de los valores hasta i – 1 es igual a la suma de los valores desde i + 1 hasta n .
- La suma de los valores hasta i es igual a la suma de los valores desde i + 1 hasta n .
- La suma de los valores hasta i – 1 es igual a la suma de los valores desde i hasta n .
- Si alguna de las condiciones anteriores se cumple para cualquier punto dado, entonces la línea existe.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Function that returns true if
// the required line exists
bool lineExists(int x[], int y[],
int v[], int n)
{
// To handle negative values from x[]
int size = (2 * MAX) + 1;
long arr[size] = { 0 };
// Update arr[] such that arr[i] contains
// the sum of all v[j] such that x[j] = i
// for all valid values of j
for (int i = 0; i < n; i++) {
arr[x[i] + MAX] += v[i];
}
// Update arr[i] such that arr[i] contains
// the sum of the subarray arr[0...i]
// from the original array
for (int i = 1; i < size; i++)
arr[i] += arr[i - 1];
// If all the points add to 0 then
// the line can be drawn anywhere
if (arr[size - 1] == 0)
return true;
// If the line is drawn touching the
// leftmost possible points
if (arr[size - 1] - arr[0] == 0)
return true;
for (int i = 1; i < size - 1; i++) {
// If the line is drawn just before
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i - 1])
return true;
// If the line is drawn touching
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i])
return true;
// If the line is drawn just after
// the current point
if (arr[i] == arr[size - 1] - arr[i])
return true;
}
// If the line is drawn touching the
// rightmost possible points
if (arr[size - 2] == 0)
return true;
return false;
}
// Driver code
int main()
{
int x[] = { -3, 5, 8 };
int y[] = { 8, 7, 9 };
int v[] = { 8, 2, 10 };
int n = sizeof(x) / sizeof(int);
if (lineExists(x, y, v, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int MAX = 1000;
// Function that returns true if
// the required line exists
static boolean lineExists(int x[], int y[],
int v[], int n)
{
// To handle negative values from x[]
int size = (2 * MAX) + 1;
long []arr = new long[size];
// Update arr[] such that arr[i] contains
// the sum of all v[j] such that x[j] = i
// for all valid values of j
for (int i = 0; i < n; i++)
{
arr[x[i] + MAX] += v[i];
}
// Update arr[i] such that arr[i] contains
// the sum of the subarray arr[0...i]
// from the original array
for (int i = 1; i < size; i++)
arr[i] += arr[i - 1];
// If all the points add to 0 then
// the line can be drawn anywhere
if (arr[size - 1] == 0)
return true;
// If the line is drawn touching the
// leftmost possible points
if (arr[size - 1] - arr[0] == 0)
return true;
for (int i = 1; i < size - 1; i++)
{
// If the line is drawn just before
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i - 1])
return true;
// If the line is drawn touching
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i])
return true;
// If the line is drawn just after
// the current point
if (arr[i] == arr[size - 1] - arr[i])
return true;
}
// If the line is drawn touching the
// rightmost possible points
if (arr[size - 2] == 0)
return true;
return false;
}
// Driver code
public static void main(String []args)
{
int x[] = { -3, 5, 8 };
int y[] = { 8, 7, 9 };
int v[] = { 8, 2, 10 };
int n = x.length;
if (lineExists(x, y, v, n))
System.out.printf("Yes");
else
System.out.printf("No");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
MAX = 1000;
# Function that returns true if
# the required line exists
def lineExists(x, y, v, n) :
# To handle negative values from x[]
size = (2 * MAX) + 1;
arr = [0] * size ;
# Update arr[] such that arr[i] contains
# the sum of all v[j] such that x[j] = i
# for all valid values of j
for i in range(n) :
arr[x[i] + MAX] += v[i];
# Update arr[i] such that arr[i] contains
# the sum of the subarray arr[0...i]
# from the original array
for i in range(1, size) :
arr[i] += arr[i - 1];
# If all the points add to 0 then
# the line can be drawn anywhere
if (arr[size - 1] == 0) :
return True;
# If the line is drawn touching the
# leftmost possible points
if (arr[size - 1] - arr[0] == 0) :
return True;
for i in range(1, size - 1) :
# If the line is drawn just before
# the current point
if (arr[i - 1] == arr[size - 1] - arr[i - 1]) :
return True;
# If the line is drawn touching
# the current point
if (arr[i - 1] == arr[size - 1] - arr[i]) :
return True;
# If the line is drawn just after
# the current point
if (arr[i] == arr[size - 1] - arr[i]) :
return True;
# If the line is drawn touching the
# rightmost possible points
if (arr[size - 2] == 0) :
return True;
return False;
# Driver code
if __name__ == "__main__" :
x = [ -3, 5, 8 ];
y = [ 8, 7, 9 ];
v = [ 8, 2, 10 ];
n = len(x);
if (lineExists(x, y, v, n)) :
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 1000;
// Function that returns true if
// the required line exists
static Boolean lineExists(int []x, int []y,
int []v, int n)
{
// To handle negative values from x[]
int size = (2 * MAX) + 1;
long []arr = new long[size];
// Update arr[] such that arr[i] contains
// the sum of all v[j] such that x[j] = i
// for all valid values of j
for (int i = 0; i < n; i++)
{
arr[x[i] + MAX] += v[i];
}
// Update arr[i] such that arr[i] contains
// the sum of the subarray arr[0...i]
// from the original array
for (int i = 1; i < size; i++)
arr[i] += arr[i - 1];
// If all the points add to 0 then
// the line can be drawn anywhere
if (arr[size - 1] == 0)
return true;
// If the line is drawn touching the
// leftmost possible points
if (arr[size - 1] - arr[0] == 0)
return true;
for (int i = 1; i < size - 1; i++)
{
// If the line is drawn just before
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i - 1])
return true;
// If the line is drawn touching
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i])
return true;
// If the line is drawn just after
// the current point
if (arr[i] == arr[size - 1] - arr[i])
return true;
}
// If the line is drawn touching the
// rightmost possible points
if (arr[size - 2] == 0)
return true;
return false;
}
// Driver code
public static void Main(String []args)
{
int []x = { -3, 5, 8 };
int []y = { 8, 7, 9 };
int []v = { 8, 2, 10 };
int n = x.Length;
if (lineExists(x, y, v, n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
const MAX = 1000;
// Function that returns true if
// the required line exists
function lineExists(x, y, v, n)
{
// To handle negative values from x[]
let size = (2 * MAX) + 1;
let arr = new Array(size).fill(0);
// Update arr[] such that arr[i] contains
// the sum of all v[j] such that x[j] = i
// for all valid values of j
for (let i = 0; i < n; i++) {
arr[x[i] + MAX] += v[i];
}
// Update arr[i] such that arr[i] contains
// the sum of the subarray arr[0...i]
// from the original array
for (let i = 1; i < size; i++)
arr[i] += arr[i - 1];
// If all the points add to 0 then
// the line can be drawn anywhere
if (arr[size - 1] == 0)
return true;
// If the line is drawn touching the
// leftmost possible points
if (arr[size - 1] - arr[0] == 0)
return true;
for (let i = 1; i < size - 1; i++) {
// If the line is drawn just before
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i - 1])
return true;
// If the line is drawn touching
// the current point
if (arr[i - 1] == arr[size - 1] - arr[i])
return true;
// If the line is drawn just after
// the current point
if (arr[i] == arr[size - 1] - arr[i])
return true;
}
// If the line is drawn touching the
// rightmost possible points
if (arr[size - 2] == 0)
return true;
return false;
}
// Driver code
let x = [-3, 5, 8];
let y = [8, 7, 9]
let v = [8, 2, 10];
let n = x.length;
if (lineExists(x, y, v, n))
document.write("Yes");
else
document.write("No");
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
Yes
Complejidad de tiempo: O(N), donde N es igual al tamaño = (2*MAX) + 1
Espacio auxiliar: O(N), donde N es igual al tamaño = (2*MAX) + 1
Publicación traducida automáticamente
Artículo escrito por AshaRamMeena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA