fork download
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct {
  5. int x;
  6. int type; // 1 for left edge, -1 for right edge
  7. int bottomY;
  8. int topY;
  9. } Event;
  10.  
  11. int compare(const void *a, const void *b) {
  12. Event *eventA = (Event *)a;
  13. Event *eventB = (Event *)b;
  14. if (eventA->x != eventB->x) {
  15. return eventA->x - eventB->x;
  16. }
  17. return eventA->type - eventB->type; // Left edge before right edge
  18. }
  19.  
  20. int calculate_y_length(Event *events, int active_count) {
  21. int total_length = 0;
  22. int current_start = -1;
  23. int current_end = -1;
  24.  
  25. for (int i = 0; i < active_count; i++) {
  26. if (events[i].bottomY > current_end) {
  27. // Non-overlapping interval
  28. if (current_start != -1) {
  29. total_length += current_end - current_start;
  30. }
  31. current_start = events[i].bottomY;
  32. current_end = events[i].topY;
  33. } else {
  34. // Overlapping interval
  35. if (events[i].topY > current_end) {
  36. current_end = events[i].topY;
  37. }
  38. }
  39. }
  40.  
  41. // Add last active interval
  42. if (current_start != -1) {
  43. total_length += current_end - current_start;
  44. }
  45.  
  46. return total_length;
  47. }
  48.  
  49. int main() {
  50. int N, K, L;
  51. scanf("%d %d %d", &N, &K, &L);
  52.  
  53. Event *events = malloc(2 * N * sizeof(Event));
  54. for (int i = 1; i <= N; i++) {
  55. int leftX = i * K - L;
  56. int rightX = i * K + L;
  57. int bottomY = i * K;
  58. int topY = i * K + L;
  59.  
  60. // Left edge event
  61. events[2 * (i - 1)] = (Event){leftX, 1, bottomY, topY};
  62. // Right edge event
  63. events[2 * (i - 1) + 1] = (Event){rightX, -1, bottomY, topY};
  64. }
  65.  
  66. qsort(events, 2 * N, sizeof(Event), compare);
  67.  
  68. int area = 0;
  69. int last_x = events[0].x;
  70. Event *active_intervals = malloc(2 * N * sizeof(Event));
  71. int active_count = 0;
  72.  
  73. for (int i = 0; i < 2 * N; i++) {
  74. int x = events[i].x;
  75.  
  76. // Calculate area contribution from last_x to current x
  77. if (active_count > 0) {
  78. int y_length = calculate_y_length(active_intervals, active_count);
  79. area += y_length * (x - last_x);
  80. }
  81.  
  82. // Update active intervals
  83. if (events[i].type == 1) { // Left edge
  84. active_intervals[active_count++] = events[i];
  85. } else { // Right edge
  86. for (int j = 0; j < active_count; j++) {
  87. if (active_intervals[j].bottomY == events[i].bottomY &&
  88. active_intervals[j].topY == events[i].topY) {
  89. // Remove the interval
  90. active_intervals[j] = active_intervals[--active_count];
  91. break;
  92. }
  93. }
  94. }
  95.  
  96. last_x = x;
  97. }
  98.  
  99. printf("%d\n", area);
  100. free(events);
  101. free(active_intervals);
  102. return 0;
  103. }
Success #stdin #stdout 0.02s 25820KB
stdin
Standard input is empty
stdout
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int type; // 1 for left edge, -1 for right edge
    int bottomY;
    int topY;
} Event;

int compare(const void *a, const void *b) {
    Event *eventA = (Event *)a;
    Event *eventB = (Event *)b;
    if (eventA->x != eventB->x) {
        return eventA->x - eventB->x;
    }
    return eventA->type - eventB->type; // Left edge before right edge
}

int calculate_y_length(Event *events, int active_count) {
    int total_length = 0;
    int current_start = -1;
    int current_end = -1;

    for (int i = 0; i < active_count; i++) {
        if (events[i].bottomY > current_end) {
            // Non-overlapping interval
            if (current_start != -1) {
                total_length += current_end - current_start;
            }
            current_start = events[i].bottomY;
            current_end = events[i].topY;
        } else {
            // Overlapping interval
            if (events[i].topY > current_end) {
                current_end = events[i].topY;
            }
        }
    }

    // Add last active interval
    if (current_start != -1) {
        total_length += current_end - current_start;
    }

    return total_length;
}

int main() {
    int N, K, L;
    scanf("%d %d %d", &N, &K, &L);
    
    Event *events = malloc(2 * N * sizeof(Event));
    for (int i = 1; i <= N; i++) {
        int leftX = i * K - L;
        int rightX = i * K + L;
        int bottomY = i * K;
        int topY = i * K + L;

        // Left edge event
        events[2 * (i - 1)] = (Event){leftX, 1, bottomY, topY};
        // Right edge event
        events[2 * (i - 1) + 1] = (Event){rightX, -1, bottomY, topY};
    }

    qsort(events, 2 * N, sizeof(Event), compare);

    int area = 0;
    int last_x = events[0].x;
    Event *active_intervals = malloc(2 * N * sizeof(Event));
    int active_count = 0;

    for (int i = 0; i < 2 * N; i++) {
        int x = events[i].x;

        // Calculate area contribution from last_x to current x
        if (active_count > 0) {
            int y_length = calculate_y_length(active_intervals, active_count);
            area += y_length * (x - last_x);
        }

        // Update active intervals
        if (events[i].type == 1) { // Left edge
            active_intervals[active_count++] = events[i];
        } else { // Right edge
            for (int j = 0; j < active_count; j++) {
                if (active_intervals[j].bottomY == events[i].bottomY &&
                    active_intervals[j].topY == events[i].topY) {
                    // Remove the interval
                    active_intervals[j] = active_intervals[--active_count];
                    break;
                }
            }
        }

        last_x = x;
    }

    printf("%d\n", area);
    free(events);
    free(active_intervals);
    return 0;
}