> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-2-solutions/c-safe-houses.md).

# C: Safe Houses

https\://open.kattis.com/problems/safehouses

* For every house-spy pair with coordinates $$(x\_h,y\_h)$$and $$(x\_s,y\_s)$$, calculate the distance as $$|x\_h-x\_s| + |y\_h-y\_s|$$. All pairwise distances can be computed this way in quadratic time. 

{% hint style="warning" %}
Note that if the size of the grid is $$N\times N$$, there are at most $$\mathcal{O} (N^2)$$houses and spies. So, computing all pairwise distances can be done in $$\mathcal{O} (N^4)$$, which is fast enough to fit in the time limit.
{% endhint %}

* Now, for each spy, compute the distance to the closest house. Report the minimum such value.