Fence Painting

Análisis oficial (Java)

Solución 1 (análisis por casos)

Solución

Complejidad temporal: $\mathcal O(1)$

Podemos partir en casos según los seis órdenes posibles de $a,b,c,d$ . Los casos son:

$a\le c$
- $b<c$
- $c\le b<d$
- $d\le b$
$a>c$
- $d<a$
- $a\le d < b$
- $b\le d$

Para cada caso, la respuesta es una combinación lineal distinta de $a,b,c,d$ .

Implementación

C++JavaPython


#include <iostream>
 
void set_up(std::string name) {
	freopen((name + ".in").c_str(), "r", stdin);
	freopen((name + ".out").c_str(), "w", stdout);
}
 
int main() {
	set_up("paint");
	int a, b, c, d;
	std::cin >> a >> b >> c >> d;
 
	if (a <= c) {
		if (b < c) {
			std::cout << b - a + d - c;
		} else if (b < d) {
			std::cout << d - a;
		} else {
			std::cout << b - a;
		}
	} else {
		if (d < a) {
			std::cout << b - a + d - c;
		} else if (d < b) {
			std::cout << b - c;
		} else {
			std::cout << d - c;
		}
	}
}


import java.io.*;
import java.util.*;
 
public class FencePainting {
 
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("paint");
		int a = io.nextInt();
		int b = io.nextInt();
		int c = io.nextInt();
		int d = io.nextInt();
 
		if (a <= c) {
			if (b < c) {
				io.print(b - a + d - c);
			} else if (b < d) {
				io.print(d - a);
			} else {
				io.print(b - a);
			}
		} else {
			if (d < a) {
				io.print(b - a + d - c);
			} else if (d < b) {
				io.print(b - c);
			} else {
				io.print(d - c);
			}
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import sys
 
sys.stdin = open("paint.in", "r")
sys.stdout = open("paint.out", "w")
 
 
def solve(a, b, c, d):
	if a <= c:
		if b < c:
			return b - a + d - c
		elif b < d:
			return d - a
		else:
			return b - a
	else:
		if d < a:
			return b - a + d - c
		elif d < b:
			return b - c
		else:
			return d - c
 
 
a, b = map(int, input().split())
c, d = map(int, input().split())
 
print(solve(a, b, c, d))

Implementación condensada

Podemos simplificar la implementación de arriba reutilizando lógica entre casos. Por ejemplo,

No hace falta tener cadenas de ifs separadas para los casos $a\ge c$ y $a<c$ . Si estamos en el segundo caso, podemos intercambiar los dos intervalos para transformarlo en el primero, sin cambiar la respuesta.
Podemos reemplazar el if que compara $b$ y $d$ por $\max(b,d)$ .

C++JavaPython


#include <iostream>
 
void set_up(std::string name) {
	freopen((name + ".in").c_str(), "r", stdin);
	freopen((name + ".out").c_str(), "w", stdout);
}
 
int main() {
	set_up("paint");
	int a, b, c, d;
	std::cin >> a >> b >> c >> d;
 
	if (a > c) {
		std::swap(a, c);
		std::swap(b, d);
	}
 
	if (b < c) {
		std::cout << b - a + d - c;
	} else {
		std::cout << std::max(b, d) - a;
	}
}


import java.io.*;
import java.util.*;
 
public class FencePainting {
 
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("paint");
		int a = io.nextInt();
		int b = io.nextInt();
		int c = io.nextInt();
		int d = io.nextInt();
 
		if (a > c) {
			int tempA = a;
			a = c;
			c = tempA;
 
			int tempB = b;
			b = d;
			d = tempB;
		}
 
		if (b < c) {
			io.print(b - a + d - c);
		} else {
			io.print(Math.max(b, d) - a);
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import sys
 
sys.stdin = open("paint.in", "r")
sys.stdout = open("paint.out", "w")
 
 
def solve(a, b, c, d):
	if a > c:
		a, b, c, d = c, d, a, b
	if b < c:
		return b - a + d - c
	return max(b, d) - a
 
 
a, b = map(int, input().split())
c, d = map(int, input().split())
 
print(solve(a, b, c, d))

Otras soluciones

Ver el módulo Geometría de rectángulos.