#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); 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}; } int area = 0; int last_x = events[0].x; 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; } free(events); free(active_intervals); return 0; }
Standard input is empty
#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;
}