fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /**
  5.  * @brief Find largest rectangle for a new window in a canvas with some existing windows.
  6.  * @param width Canvas width in pixel
  7.  * @param height Canvas height in pixel
  8.  * @param objects Existing objects, in the form {{x_topleft,y_topleft,x_bottomright_y_bottomright},...}
  9.  * @param num_objects Number of objects in previous parameter
  10.  * @param output Array to store result as {x_topleft,y_topleft,x_bottomright_y_bottomright}
  11.  */
  12. void find_largest_rect(int width, int height, int (*objects)[4],
  13.                        int num_objects, int* output) {
  14.     // create canvas array
  15.     unsigned char* canvas = (unsigned char*)malloc(width * height * sizeof(
  16.                                 unsigned char));
  17.     int* up         = (int*)malloc(width * sizeof(int));
  18.     int* up_last    = (int*)malloc(width * sizeof(int));
  19.     int* left       = (int*)malloc(width * sizeof(int));
  20.     int* left_last  = (int*)malloc(width * sizeof(int));
  21.     int* right      = (int*)malloc(width * sizeof(int));
  22.     int* right_last = (int*)malloc(width * sizeof(int));
  23.     int ans = 0, lo = 0, ro = 0;
  24.     int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
  25.     int i = 0, j = 0, k = 0;
  26.  
  27.     // set whole canvas to 1
  28.     for (i = 0; i < height; i++)
  29.         for (j = 0; j < width; j++) {
  30.             canvas[i * (width) + j] = 1;
  31.         }
  32.  
  33.     // initialize temp vars
  34.     for (j = 0; j < width; j++) {
  35.         up[j] = 0;
  36.         up_last[j] = 0;
  37.         left[j] = 0;
  38.         left_last[j] = 0;
  39.         right[j] = 0;
  40.         right_last[j] = 0;
  41.     }
  42.  
  43.     // set occupied points to 0
  44.     for (i = 0; i < num_objects; i++) {
  45.         x1 = objects[i][0];
  46.         y1 = objects[i][1];
  47.         x2 = objects[i][2];
  48.         y2 = objects[i][3];
  49.  
  50.         // boundary check
  51.         x1 = x1 < 0 ? 0 : (x1 > width ? width : x1);
  52.         y1 = y1 < 0 ? 0 : (y1 > height ? height : y1);
  53.         x2 = x2 < 0 ? 0 : (x2 > width ? width : x2);
  54.         y2 = y2 < 0 ? 0 : (y2 > height ? height : y2);
  55.  
  56.         for (j = y1; j <= y2; j++) {
  57.             for (k = x1; k <= x2; k++) {
  58.                 canvas[j * (width) + k] = 0;
  59.             }
  60.         }
  61.     }
  62.  
  63.     x1 = 0, y1 = 0, x2 = 0, y2 = 0;
  64.  
  65.     for (i = 0; i < height; i++) {
  66.         lo = -1;
  67.         ro = width;
  68.  
  69.         // store last temp vars
  70.         for (j = 0; j < width; j++) {
  71.             up_last[j] = up[j];
  72.             left_last[j] = left[j];
  73.             right_last[j] = right[j];
  74.         }
  75.  
  76.         // initialize up[] and left[] for current i
  77.         for (j = 0; j < width; j++) {
  78.             if (canvas[i * width + j] == 0) {
  79.                 left[j] = up[j] = 0;
  80.                 lo = j;
  81.             }
  82.             else {
  83.                 up[j] = (i == 0) ? 1 : up_last[j] + 1;
  84.                 left[j] = (i == 0) ? lo + 1 : ((left_last[j] > lo + 1) ?
  85.                                                left_last[j] : lo + 1);
  86.             }
  87.         }
  88.  
  89.         for (j = width - 1; j >= 0; j--) {
  90.             if (canvas[i * width + j] == 0) {
  91.                 right[j] = width;
  92.                 ro = j;
  93.             }
  94.             else {
  95.                 right[j] = (i == 0) ? ro - 1 : ((right_last[j] < ro - 1) ?
  96.                                                 right_last[j] : ro - 1);
  97.             }
  98.  
  99.             if (up[j] * (right[j] - left[j] + 1) > ans) {
  100.                 ans = up[j] * (right[j] - left[j] + 1);
  101.                 x1 = left[j];
  102.                 y1 = i - up[j] + 1;
  103.                 x2 = j;
  104.                 y2 = i;
  105.             }
  106.         }
  107.     }
  108.  
  109.     output[0] = x1;
  110.     output[1] = y1;
  111.     output[2] = x2;
  112.     output[3] = y2;
  113.  
  114.     printf("Max rectangle area = %d\n", ans);
  115.  
  116.     // print canvas
  117.     //    for (i = 0; i < height; i++) {
  118.     //        printf("%d\t", i);
  119.  
  120.     //        for (j = 0; j < width; j++) {
  121.     //            printf("%d", *(canvas + i * (width) + j));
  122.     //        }
  123.  
  124.     //        printf("\n");
  125.     //    }
  126.  
  127.     free(canvas);
  128.     free(up);
  129.     free(up_last);
  130.     free(left);
  131.     free(left_last);
  132.     free(right);
  133.     free(right_last);
  134. }
  135.  
  136. int main(void) {
  137.     //canvas properties
  138.     int width = 30;
  139.     int height = 20;
  140.  
  141.     // objects in canvas
  142.     int num_objects = 3;
  143.     int objects[3][4] = {{0, 0, 9, 9}, {20, 0, 29, 19}, {5, 14, 14, 18}};
  144.  
  145.     // var to store result coordinates of topleft and bottomright vertices (x1,y1,x2,y2)
  146.     int output[4] = {0, 0, 0, 0};
  147.  
  148.     find_largest_rect(width, height, objects, num_objects, output);
  149.  
  150.     printf("(%d,%d)->(%d,%d)\n", output[0], output[1], output[2], output[3]);
  151.  
  152.     return 0;
  153. }
  154.  
Success #stdin #stdout 0s 2380KB
comments (?)
stdin 
Standard input is empty
stdout 
Max rectangle area = 140
(10,0)->(19,13)
https://ideone.com/RqcJkM
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

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!