/*
Time limit: 5000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_DIM 100
// Vector ADT
struct Vector {
int *coords;
int dim;
};
// Function prototypes
// create a vector with given dimension
struct Vector create_vector(int dim);
// free the memory allocated for a vector
void free_vector(struct Vector v);
// set the coordinate at given index
void set_coord(struct Vector v, int index, int value);
// get the coordinate at given index
int get_coord(struct Vector v, int index);
// calculate the squared Euclidean distance between two vectors
long long squared_distance(struct Vector v1, struct Vector v2);
// find the index of the nearest vector in the array to the query vector
int find_nearest_vector(struct Vector *vectors, int n, struct Vector query);
/**
* @brief Create a vector with given dimension
* @param dim dimension of the vector
* @return a Vector struct
*/
struct Vector create_vector(int dim) {
struct Vector v;
v.dim = dim;
v.coords = (int *)malloc(dim * sizeof(int));
memset(v.coords, 0, dim * sizeof(int));
return v;
}
/**
* @brief Free the memory allocated for a vector
* @param v a Vector struct
*/
void free_vector(struct Vector v) {
free(v.coords);
}
/**
* @brief Set the coordinate at given index
* @param v a Vector struct
* @param index the index of the coordinate
* @param value the value to set
*/
void set_coord(struct Vector v, int index, int value) {
v.coords[index] = value;
}
/**
* @brief Get the coordinate at given index
* @param v a Vector struct
* @param index the index of the coordinate
* @return the value at the given index
*/
int get_coord(struct Vector v, int index) {
return v.coords[index];
}
/**
* @brief Calculate squared Euclidean distance between two vectors
* @param v1 first vector
* @param v2 second vector
* @return squared distance
* @note assumes both vectors have the same dimension
*/
long long squared_distance(struct Vector v1, struct Vector v2) {
// WRITE YOUR CODE HERE
}
/**
* @brief Find the index of the nearest vector in the array to the query vector
* @param vectors array of vectors
* @param n number of vectors in the array
* @param query the query vector
* @return index of the nearest vector (0-based)
*/
int find_nearest_vector(struct Vector *vectors, int n, struct Vector query) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
int n, d, q;
scanf("%d %d %d", &n, &d, &q);
// Read anomaly vectors
struct Vector *vectors = (struct Vector *)malloc(n * sizeof(struct Vector));
for (int i = 0; i < n; i++) {
vectors[i] = create_vector(d);
for (int j = 0; j < d; j++) {
int coord;
scanf("%d", &coord);
set_coord(vectors[i], j, coord);
}
}
// Process queries
for (int i = 0; i < q; i++) {
struct Vector query = create_vector(d);
for (int j = 0; j < d; j++) {
int coord;
scanf("%d", &coord);
set_coord(query, j, coord);
}
int nearest = find_nearest_vector(vectors, n, query);
printf("%d\n", nearest);
free_vector(query);
}
// Free memory
for (int i = 0; i < n; i++) {
free_vector(vectors[i]);
}
free(vectors);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Nearest Neighbor Search
In this problem, you need to implement a Vector ADT that supports distance computation and nearest neighbor search. Given $n$ vectors in $d$-dimensional space and $q$ query vectors, for each query, find the index of the vector that has the minimum squared Euclidean distance to it.
The squared Euclidean distance between two $d$-dimensional vectors $\mathbf{a} = (a_1, a_2, \ldots, a_d)$ and $\mathbf{b} = (b_1, b_2, \ldots, b_d)$ is defined as:
$$\text{dist}^2(\mathbf{a}, \mathbf{b}) = \sum_{i=1}^{d} (a_i - b_i)^2$$
The Vector ADT should support the following operations:
- `create_vector(int dim)`: Create a new vector with dimension `dim`.
- `free_vector(Vector v)`: Free the memory used by the vector.
- `set_coord(Vector v, int index, int value)`: Set the coordinate at position `index` to `value`.
- `get_coord(Vector v, int index)`: Get the coordinate at position `index`.
- `squared_distance(Vector v1, Vector v2)`: Compute the squared Euclidean distance between two vectors.
- `find_nearest_vector(Vector *vectors, int n, Vector query)`: Find the index of the nearest vector to the query vector.
Note that some operations have been implemented in the given code template. You need to implement the `find_nearest_vector` function.
### Input
- First line contains three integers $n$, $d$, and $q$ ($1 \leq n \leq 1000$, $1 \leq d \leq 100$, $1 \leq q \leq 1000$):
- $n$: number of vectors
- $d$: dimension of each vector
- $q$: number of queries
- Next $n$ lines: each line contains $d$ integers representing a vector. All coordinates are in range $[-1000, 1000]$.
- Next $q$ lines: each line contains $d$ integers representing a query vector. All coordinates are in range $[-1000, 1000]$.
### Output
For each query, output a single integer — the index (0-based) of the nearest vector. If there are multiple vectors with the same minimum distance, output the smallest index.
### Example
**Input**
```
3 2 2
1 2
4 5
2 3
3 4
1 1
```
**Output**
```
1
0
```
**Explanation**
For query vector $(3, 4)$:
- Vector 0 at $(1, 2)$: squared distance $= (3-1)^2 + (4-2)^2 = 4 + 4 = 8$
- Vector 1 at $(4, 5)$: squared distance $= (3-4)^2 + (4-5)^2 = 1 + 1 = 2$
- Vector 2 at $(2, 3)$: squared distance $= (3-2)^2 + (4-3)^2 = 1 + 1 = 2$
Minimum distance is 2, achieved by vectors 1 and 2. Output the smaller index: **1**.
For query vector $(1, 1)$:
- Vector 0 at $(1, 2)$: squared distance $= (1-1)^2 + (1-2)^2 = 0 + 1 = 1$
- Vector 1 at $(4, 5)$: squared distance $= (1-4)^2 + (1-5)^2 = 9 + 16 = 25$
- Vector 2 at $(2, 3)$: squared distance $= (1-2)^2 + (1-3)^2 = 1 + 4 = 5$
Minimum distance is 1, at vector 0. Output: **0**.