#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#if 0
  #define PART part1
#else
  #define PART part2
#endif

#if 0
  #define FILENAME "sample.txt"
  #define TARGET_Y 10
  #define UPPER 20
#else
  #define FILENAME "input.txt"
  #define TARGET_Y 2000000
  #define UPPER 2000000
#endif

#define LOWER 1000000

#define ENTRIES_CAP 30
#define CAP 10000000
#define OFFSET (CAP/2)

int sensors[CAP][2];
int beacons[CAP][2];
size_t entries = 0;

int obj[CAP];
int row[CAP];

size_t sum = 0;

#define MAX(x, y) (((x) > (y)) ? (x) : (y))

int taxi_distance(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + abs(y1 - y2);
}

void analyze(int target_y)
{
    memset(obj, 0, sizeof(obj));
    memset(row, 0, sizeof(row));

    for(size_t i = 0; i < entries; i++)
    {
        int x1 = sensors[i][0]; int x2 = beacons[i][0];
        int y1 = sensors[i][1]; int y2 = beacons[i][1];

        int r = taxi_distance(x1, y1, x2, y2);
        int diff = abs(target_y - y1);
        for(int i = x1 - (r - diff); i <= x1 + (r - diff); i++) {
            row[i + OFFSET] = 1;
        }

        if(y2 == target_y) obj[x2 + OFFSET] = 1;
    }
}

void part1()
{
    analyze(TARGET_Y);

    for(size_t i = 0; i < CAP; i++)
        if(row[i] - obj[i] > 0) sum++;
}

void part2()
{
    for(int y = LOWER; y <= UPPER; y++)
    {
        printf("%d\n", y);
        analyze(y);

        for(int x = LOWER; x <= UPPER; x++)
            if(row[x + OFFSET] == 0 && obj[x + OFFSET] == 0) {
                sum = (x * 4000000) + y;
                return;
            }
    }

    exit(1);
}

void parse_xy(char *str, int *x, int *y, int nth)
{
    char *s, *sx;
    char *y_str, *x_str;

    x_str = strtok_r(strtok_r(str, ",", &s), " ", &sx);
    y_str = strtok_r(NULL, ",", &s);

    for(int i = 1; i < nth; i++)
        x_str = strtok_r(NULL, " ", &sx);

    assert(x_str != NULL);
    assert(y_str != NULL);

    *x = atoi(&(x_str[2]));
    *y = atoi(&(y_str[3]));
}

void parse()
{
    FILE *fp = fopen(FILENAME, "r");
    if(!fp) {
        fprintf(stderr, "ERROR: Could not open file: %s\n", FILENAME);
        exit(1);
    }

    char line[512];
    while(fgets(line, sizeof(line), fp))
    {
        size_t len = strlen(line);
        if(line[len-1] == '\n') line[len-1] = 0;

        parse_xy(strtok(line, ":"), &sensors[entries][0], &sensors[entries][1], 3);
        parse_xy(strtok(NULL, ":"), &beacons[entries][0], &beacons[entries][1], 5);
        entries++;
    }

    fclose(fp);
}

int main(void)
{
    parse();
    PART();
    printf("%ld\n", sum);
    return 0;
}