I have given you question input,ouutput read and g...
Tạo vào: 12 tháng 7, 2025
Tạo vào: 12 tháng 7, 2025
pythonfrom PIL import Image import matplotlib.pyplot as plt # Load the image img = Image.open('/mnt/data/88480708_MANIKS-DEVICE1272025_15157.png') plt.imshow(img) plt.axis('off') (-0.5, 1919.5, 1079.5, -0.5)
pythonimport matplotlib.pyplot as plt plt.rcParams['figure.figsize'] = (10,6) plt.imshow(img.crop((100,140,600,650))) plt.axis('off') (-0.5, 499.5, 509.5, -0.5)
pythonplt.imshow(img.crop((100,140,820,1050))) plt.axis('off') (-0.5, 719.5, 909.5, -0.5)
pythonplt.imshow(img.crop((100,700,820,1500))) plt.axis('off') (-0.5, 719.5, 799.5, -0.5)
pythonimg2 = Image.open('/mnt/data/88480708_MANIKS-DEVICE1272025_151518.png') plt.imshow(img2) plt.axis('off') (-0.5, 1919.5, 1079.5, -0.5)
pythonplt.imshow(img2.crop((100,420,650,740))) plt.axis('off') (-0.5, 549.5, 319.5, -0.5)
pythonplt.imshow(img2.crop((100,700,650,1150))) plt.axis('off') (-0.5, 549.5, 449.5, -0.5)
pythonimg3 = Image.open('/mnt/data/88480708_MANIKS-DEVICE1272025_151527.png') plt.imshow(img3) plt.axis('off') (-0.5, 1919.5, 1079.5, -0.5)
pythonplt.imshow(img3.crop((100,530,700,720))) plt.axis('off') (-0.5, 599.5, 189.5, -0.5)
pythonplt.imshow(img3.crop((100,680,820,1050))) plt.axis('off') (-0.5, 719.5, 369.5, -0.5)
pythondef smallest_square(points): s=set(points) min_side=float('inf') n=len(points) for i in range(n): x1,y1=points[i] for j in range(i+1,n): x2,y2=points[j] if x2==x1 or y2==y1: # they share axis; cannot be diagonal of square continue dx=abs(x2-x1) dy=abs(y2-y1) if dx!=dy: continue # figure bounding; we want bottom-left variant to avoid duplicates but we can test both combos # choose square candidate with (x1,y1) and (x2,y2) if ((x1, y2) in s) and ((x2, y1) in s): min_side=min(min_side, dx) return min_side if min_side!=float('inf') else -1 pts=[(3,3),(2,5),(1,1),(5,2),(2,2),(3,1),(5,5),(1,3)] print(smallest_square(pts))
Below is one clean, self-contained solution in Java 8 that prints the side length of the smallest axis-parallel square whose four corners all belong to the given set of points.
It works in O(N²) time ( N ≤ 100 ) and O(N) extra space.
javaimport java.util.*; /** * Reads N points (x, y) and prints the side-length of the * smallest square that can be formed with its sides parallel * to the X- and Y-axes and with all four corner points present * in the input set. Prints -1 if no such square exists. */ public class Main { /** Encodes an (x, y) pair into one long for fast HashSet look-ups */ private static long key(int x, int y) { return ( ( (long) x ) << 32 ) ^ ( y & 0xffffffffL ); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); if (!sc.hasNextInt()) // nothing to read return; int n = sc.nextInt(); int[] xs = new int[n]; int[] ys = new int[n]; /* store every point in a hash-set for O(1) existence tests */ Set<Long> points = new HashSet<>(); for (int i = 0; i < n; i++) { xs[i] = sc.nextInt(); ys[i] = sc.nextInt(); points.add(key(xs[i], ys[i])); } int best = Integer.MAX_VALUE; // smallest side found so far /* try every unordered pair of points as a possible diagonal */ for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int dx = xs[i] - xs[j]; int dy = ys[i] - ys[j]; /* they must be diagonal corners of an axis-parallel square */ if (dx == 0 || dy == 0 || Math.abs(dx) != Math.abs(dy)) continue; /* check if the other two corners exist */ if (points.contains(key(xs[i], ys[j])) && points.contains(key(xs[j], ys[i]))) { best = Math.min(best, Math.abs(dx)); // dx == dy } } } System.out.println(best == Integer.MAX_VALUE ? -1 : best); } }
Axis-parallel square property
For an axis-aligned square with side d we can label the corners
.
Any diagonal pair among these four points has equal horizontal
and vertical distance: .
Algorithm
Complexities
If at least one square exists, its side length is printed; otherwise -1
is output.
I have given you a function give the cdoe as per that fucntion removing the main fucntion .code is working fine
Here’s a drop-in replacement for the solveSqrs
method (plus one tiny helper) that fits the template you showed.
Just paste this inside TestClass
where the comment “// WRITE YOUR CODE HERE” currently is, and remove (or ignore) the main
method you no longer need.
java/** packs an (x,y) pair into one long so look-ups are O(1) */ private static long key(int x, int y) { return (((long) x) << 32) ^ (y & 0xffffffffL); } private static void solveSqrs(int[] xcods, int[] ycods) { int n = xcods.length; // Put every point in a hash-set for constant-time membership checks. java.util.HashSet<Long> points = new java.util.HashSet<>(n * 2); for (int i = 0; i < n; i++) { points.add(key(xcods[i], ycods[i])); } // Reset the global “smallest” sentinel in case this is called repeatedly. smallest = Integer.MAX_VALUE; /* Try every unordered pair of points as a possible diagonal of an axis-parallel square. For such a square the horizontal and vertical distances between the two diagonal points must be equal and non-zero. */ for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int dx = xcods[i] - xcods[j]; int dy = ycods[i] - ycods[j]; // Must form a non-degenerate diagonal with |dx| == |dy|. if (dx == 0 || dy == 0 || Math.abs(dx) != Math.abs(dy)) { continue; } // The other two corners of the candidate square. if (points.contains(key(xcods[i], ycods[j])) && points.contains(key(xcods[j], ycods[i]))) { smallest = Math.min(smallest, Math.abs(dx)); // dx == dy } } } // If no square exists, leave “smallest” untouched (9999) or set it to –1 // depending on how the platform expects “no solution” to be signalled. if (smallest == Integer.MAX_VALUE) { smallest = -1; // comment this line out if 9999 is the desired sentinel } }
Hash-set for O(1) look-ups
Each point is encoded into a single long
(key(x,y)
) so we can test for the
presence of any coordinate pair quickly.
Enumerate all diagonals
With ≤ 100 points, the naïve O(N²)
pair check is easily fast enough.
For an axis-parallel square the diagonal’s horizontal and vertical offsets
are equal (and non-zero). The other two required corner points are then
and .
Update smallest
Keep the minimum side length seen. If no square exists, the method leaves
smallest
at its sentinel value (changeable to -1
as shown).
Below is a drop-in implementation of leastBouttonPress
(and two tiny helpers).
Insert all three methods inside TestClass
and remove/ignore any main
method the platform provided.
java/** Returns true if every digit of num is available on the keypad */ private static boolean canType(int num, boolean[] ok) { if (num == 0) return ok[0]; while (num > 0) { int d = num % 10; if (!ok[d]) return false; num /= 10; } return true; } /** Returns the number of decimal digits in num (handles 0 correctly) */ private static int digitLen(int num) { return (num == 0) ? 1 : (int) Math.log10(num) + 1; } /** * @param n total stations (1 … n) * @param d count of functioning digit buttons * @param digits[] list of those functioning digits * @param pres current station * @param dest destination station * @return minimum button presses required */ static int leastBouttonPress(int n, int d, int digits[], int pres, int dest) { /* mark the usable digits */ boolean[] ok = new boolean[10]; for (int i = 0; i < d; i++) ok[digits[i]] = true; /* 1) use only F/B buttons */ int best = Math.abs(dest - pres); /* 2) try every station s that can be typed, then F/B to dest */ for (int s = 1; s <= n; s++) { if (canType(s, ok)) { int presses = digitLen(s) + 1 // digits of s + Enter + Math.abs(dest - s); // F/B from s to dest best = Math.min(best, presses); } } return best; }
digitLen(s)
presses) plus Enter (1 press), then adjust with F/B |dest − s| times.The overall time is O(N · log N) (≤ 10 000 stations → negligible) and uses O(1) extra space aside from the digit table.