Hottest (Hot)
Given N measurement points in the plane, each at (x_i, y_i) with temperature t_i, find a circle of radius R that maximizes the average temperature of enclosed points. Output the center of such a circle.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
Given $N$ measurement points in the plane, each at $(x_i, y_i)$ with temperature $t_i$, find a circle of radius $R$ that maximizes the average temperature of enclosed points. Output the center of such a circle.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Key Observation
The optimal circle must have at least one measurement point on or near its boundary, or two points defining its boundary. Therefore, the set of candidate centers is:
Each measurement point itself.
For each pair of points within distance $2R$, the two centers of circles of radius $R$ passing through both points.
Algorithm
For each candidate center $(c_x, c_y)$, compute the average temperature of all points within distance $R$. Return the center with the highest average.
For two points $(x_i, y_i)$ and $(x_j, y_j)$ with distance $d \le 2R$, the two candidate centers lie at: \[ \left(\frac{x_i + x_j}{2} \pm h \cdot \frac{-(y_j - y_i)}{d},\; \frac{y_i + y_j}{2} \pm h \cdot \frac{x_j - x_i}{d}\right) \] where $h = \sqrt{R^2 - d^2/4}$.
Complexity
Time: $O(N^3)$ --- $O(N^2)$ candidate centers, each evaluated in $O(N)$.
Space: $O(N)$.
For larger $N$, an $O(N^2 \log N)$ angular sweep can be used: for each point $i$, compute the angular intervals of centers that include each other point $j$ (with $d_{ij} \le 2R$), then sweep to find the maximum weighted count.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
double R;
cin >> N >> R;
vector<double> x(N), y(N), t(N);
for(int i = 0; i < N; i++){
cin >> x[i] >> y[i] >> t[i];
}
double bestAvg = -1e18;
double bestCx = 0, bestCy = 0;
// For each point as center, compute average
auto evalCenter = [&](double cx, double cy) {
double sumT = 0;
int cnt = 0;
for(int i = 0; i < N; i++){
double dx = x[i] - cx, dy = y[i] - cy;
if(dx*dx + dy*dy <= R*R + 1e-9){
sumT += t[i];
cnt++;
}
}
if(cnt > 0){
double avg = sumT / cnt;
if(avg > bestAvg){
bestAvg = avg;
bestCx = cx; bestCy = cy;
}
}
};
// Try each point as center
for(int i = 0; i < N; i++){
evalCenter(x[i], y[i]);
}
// Try each pair of points on boundary
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
double dx = x[j] - x[i], dy = y[j] - y[i];
double d2 = dx*dx + dy*dy;
if(d2 > 4*R*R + 1e-9) continue;
double mx = (x[i] + x[j]) / 2;
double my = (y[i] + y[j]) / 2;
double h = sqrt(max(0.0, R*R - d2/4));
// Perpendicular direction
double px = -dy, py = dx;
double len = sqrt(px*px + py*py);
if(len < 1e-12) continue;
px /= len; py /= len;
// Two candidate centers
evalCenter(mx + h * px, my + h * py);
evalCenter(mx - h * px, my - h * py);
}
}
cout << fixed << setprecision(6) << bestCx << " " << bestCy << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.