Cod sursa(job #2591717)

Utilizator AlexrotaruRotaru Alexandru Alexrotaru Data 31 martie 2020 00:59:18
Problema Patrate 3 Scor 5
Compilator c-64 Status done
Runda Arhiva de probleme Marime 3.74 kb
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define MOD 10007
#define M_PI 3.14159265358979323846 
#define LLINT long long

typedef struct cell {
    LLINT x, y;
    struct cell *next; 
} t_cell;

typedef struct list {
    t_cell *start;
} t_list;

typedef t_list* t_hash;
typedef LLINT (* f_hash) (LLINT);

t_list *create_list();
int push_back_list(t_list **list, LLINT x, LLINT y);
int check_list(t_list *list, LLINT x, LLINT y);

int add_hash(t_hash *hash, f_hash f, LLINT x, LLINT y);
int check_hash(t_hash *hash, f_hash f, LLINT x, LLINT y);

LLINT dist_sq(LLINT x1, LLINT y1, LLINT x2, LLINT y2);

t_list *create_list()
{
    t_list *list;

    list = (t_list *) malloc(sizeof(t_list));
    if(list == NULL) {
        return NULL;
    }
    list->start = NULL;
    return list;
}

int push_back_list(t_list **list, LLINT x, LLINT y)
{
    t_cell *cell, *aux_cell;

    if(*list == NULL) {
        *list = create_list();
        if(*list == NULL) {
            return -1;
        }
    }
    cell = (t_cell *) malloc(sizeof(t_cell));
    if(cell == NULL) {
        return -1;
    }
    cell->x = x;
    cell->y = y;
    cell->next = NULL;
    if((*list)->start == NULL) {
        (*list)->start = cell;
    }
    else {
        for(aux_cell = (*list)->start; aux_cell->next; aux_cell = aux_cell->next);
        aux_cell->next = cell;
    }
    return 0;
}

int check_list(t_list *list, LLINT x, LLINT y) {
    if(list == NULL) {
        return 0;
    }
    for(t_cell *cell = list->start; cell != NULL; cell = cell->next) {
        if(cell->x  == x && cell->y == y) {
            return 1;
        }
    }
    return 0;
}

int add_hash(t_hash *hash, f_hash f, LLINT x, LLINT y) 
{
    int p;

    p = f(x + y);
    return push_back_list(&(hash[p]), x, y);
    return -1; 
}

int check_hash(t_hash *hash, f_hash f, LLINT x, LLINT y)
{
    int p;

    p = f(x + y);
    return check_list(hash[p], x, y);
}

LLINT modulo(LLINT value)
{
    return MOD + value % MOD;
}

t_hash hash[2 * MOD + 1];

LLINT dist_sq(LLINT x1, LLINT y1, LLINT x2, LLINT y2)
{
    return (y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1);
}

LLINT readll(FILE *input)
{
    LLINT v = 0;
    char c;

    c = getc(input);
    do
    {
        v = v * 10LL + c - '0';
        c = getc(input);
        if(c == '.') {
            c = getc(input);
        }
    } while(c >= '0' && c <= '9');
   
    return v;
}

int main()
{
    FILE *input_file = fopen("patrate3.in", "r"),
         *output_file = fopen("patrate3.out", "w");
    int i, j, n, squares = 0;
    LLINT x, y, u_x, u_y, l_x, l_y, d, dx, dy, v_x[MOD], v_y[MOD];
    double ang;

    fscanf(input_file, "%d", &n);
    getc(input_file);
    for(i = 0; i < n; i++) {
        x = readll(input_file);
        y = readll(input_file);
        v_x[i] = x;
        v_y[i] = y;
        add_hash(hash, &modulo, x, y);
    }
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            if(i != j) {
                d = llround(sqrt(dist_sq(v_x[i], v_y[i], v_x[j], v_y[j]) / 2LL));
                dx = v_x[j] - v_x[i];
                dy = v_y[j] - v_y[i];
                if(dx != 0) {
                    ang = atan(((double) dy / dx));
                }
                else {
                    ang = M_PI / 2;
                }
                u_x = llround(d * cos(ang + M_PI / 4));
                u_y = llround(d * sin(ang + M_PI / 4));
                l_x = llround(d * cos(ang - M_PI / 4));
                l_y = llround(d * sin(ang - M_PI / 4));
                if(check_hash(hash, &modulo, v_x[i] + u_x, v_y[i] + u_y) && 
                   check_hash(hash, &modulo, v_x[i] + l_x, v_y[i] + l_y)) {
                    squares++;
                }
            }
        }
    }
    fprintf(output_file, "%d", squares / 2);
    fclose(input_file);
    fclose(output_file);
}