fork(17) download 
  1. import javax.swing.*;
  2. import java.awt.*;
  3. import java.awt.geom.Point2D;
  4. import java.util.*;
  5. import java.util.List;
  6.  
  7. public class Main {
  8.  
  9.     public static void main(String[] args) {
  10.         int N = 20;
  11.         int K = 4;
  12.         int minArea = Integer.MAX_VALUE;
  13.  
  14.         // generate points
  15.         List<Point2D> points = new ArrayList<Point2D>();
  16.         Random rnd = new Random(1);
  17.         for (int i = 0; i < N; ++i) {
  18.             points.add(new Point2D.Double(rnd.nextInt(100), rnd.nextInt(100)));
  19.         }
  20.  
  21.         // sort points by X
  22.         List<Point2D> sortedX = new ArrayList<Point2D>(points);
  23.         Collections.sort(sortedX, new Comparator<Point2D>() {
  24.             @Override
  25.             public int compare(Point2D o1, Point2D o2) {
  26.                 return Double.compare(o1.getX(), o2.getX());
  27.             }
  28.         });
  29.  
  30.         // sort points by Y
  31.         List<Point2D> sortedY = new ArrayList<Point2D>(points);
  32.         Collections.sort(sortedY, new Comparator<Point2D>() {
  33.             @Override
  34.             public int compare(Point2D o1, Point2D o2) {
  35.                 return Double.compare(o1.getY(), o2.getY());
  36.             }
  37.         });
  38.  
  39.         // iterate through all combinations of left and bottom edges
  40.         Point2D corner = null;
  41.         for (int i = 0; i < N - K + 1; ++i) {
  42.             for (int j = 0; j < N - K + 1; ++j) {
  43.                 Point2D leftPoint = sortedX.get(i);
  44.                 Point2D bottomPoint = sortedY.get(j);
  45.                 if (leftPoint.getX() > bottomPoint.getX() || leftPoint.getY() < bottomPoint.getY()) {
  46.                     continue;
  47.                 }
  48.                 int leftEdge = (int) leftPoint.getX() - 1;
  49.                 int bottomEdge = (int) bottomPoint.getY() - 1;
  50.                 // get points that are above and to the right of the corner
  51.                 Set<Point2D> acceptablePoints = new HashSet<Point2D>(sortedX.subList(i, N));
  52.                 acceptablePoints.retainAll(new HashSet<Point2D>(sortedY.subList(j, N)));
  53.                 if (acceptablePoints.size() < K) {
  54.                     continue; // not enough points
  55.                 }
  56.                 // calculate and sort areas
  57.                 List<Integer> areas = new ArrayList<Integer>();
  58.                 for (Point2D point : acceptablePoints) {
  59.                     int squareSide = (int) Math.max(point.getX() + 1 - leftEdge, point.getY() + 1 - bottomEdge);
  60.                     areas.add(squareSide * squareSide);
  61.                 }
  62.                 Collections.sort(areas);
  63.                 // update minArea
  64.                 int currentArea = areas.get(K - 1);
  65.                 if (minArea > currentArea) {
  66.                     minArea = currentArea;
  67.                     corner = new Point2D.Float(leftEdge, bottomEdge); // for debug only
  68.                 }
  69.             }
  70.         }
  71.         System.out.println("Min area: " + minArea);
  72.         // drawSquare(points, corner, minArea); // uncomment me
  73.     }
  74.  
  75.     public static void drawSquare(final List<Point2D> points, final Point2D sqCorner, final int minArea) {
  76.         JFrame jFrame = new JFrame("Squares");
  77.         jFrame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
  78.         final int s = 6;
  79.         jFrame.setSize(100 * s, 100 * s);
  80.         jFrame.setResizable(false);
  81.         jFrame.add(new JPanel() {
  82.             @Override
  83.             public void paint(Graphics g) {
  84.                 g.setColor(Color.WHITE);
  85.                 g.fillRect(0, 0, getWidth(), getHeight());
  86.                 g.setColor(Color.GRAY);
  87.                 int side = (int) Math.sqrt(minArea);
  88.                 g.fillRect((int) sqCorner.getX() * s - 2, (int) sqCorner.getY() * s - 2, side * s + 4, side * s + 4);
  89.                 g.setColor(Color.BLACK);
  90.                 for (Point2D point : points) {
  91.                     g.fillOval((int) point.getX() * s - 2, (int) point.getY() * s - 2, 4, 4);
  92.                 }
  93.             }
  94.         });
  95.         jFrame.setVisible(true);
  96.     }
  97. }
  98.  
Success #stdin #stdout 0.12s 320448KB
comments (?)
stdin 
Standard input is empty
stdout 
Min area: 324
https://ideone.com/139C7A
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!