Geometric Graphs
The problem gives you coordinates, circles, and distances. No adjacency list. No edge weights. Just geometry on a plane. Your job: decide what "connected" means, then build the graph yourself.
Problem: ARC064-C Cosmic Rays
You travel from point \((sx, sy)\) to point \((ex, ey)\) on a 2D plane. There are \(N\) circles on the plane. Inside any circle, you're shielded from cosmic rays (cost 0). Outside all circles, you accumulate exposure equal to the Euclidean distance traveled. Minimize total exposure.
Constraints: \(1 \le N \le 1000\), coordinates up to \(10^9\).
From Geometry to Graph
You can move freely inside circles. The only cost is traveling through the gaps between circles (or between start/end and a circle). This means:
- You never need to travel through the interior of a circle in a suboptimal way.
- The only thing that matters is which circles you visit and in what order.
Nodes: \(N + 2\) nodes total. One per circle plus the start point and end point.
Edge weight between two circles \(i\) and \(j\):
If the circles overlap or touch, the gap is zero — free travel. If they're separated, you pay for the gap.
Start and end are circles of radius 0.
💡 Key insight. Points and circles become nodes. The gap between them becomes the edge weight. Overlapping circles have zero-weight edges. The geometry collapses into a weighted complete graph.
Dijkstra on the Complete Graph
With \(N + 2 \le 1002\) nodes and \(O(N^2)\) edges, Dijkstra runs in \(O(N^2 \log N)\) — perfectly fine.
#include <bits/stdc++.h>
using namespace std;
int main() {
double sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
int N;
cin >> N;
// Node 0 = start, nodes 1..N = circles, node N+1 = end
int total = N + 2;
vector<double> cx(total), cy(total), cr(total);
cx[0] = sx; cy[0] = sy; cr[0] = 0;
for (int i = 1; i <= N; i++)
cin >> cx[i] >> cy[i] >> cr[i];
cx[N+1] = ex; cy[N+1] = ey; cr[N+1] = 0;
// Dijkstra
vector<double> dist(total, 1e18);
vector<bool> done(total, false);
priority_queue<pair<double,int>,
vector<pair<double,int>>,
greater<>> pq;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (done[u]) continue;
done[u] = true;
for (int v = 0; v < total; v++) {
if (done[v]) continue;
double dx = cx[u] - cx[v];
double dy = cy[u] - cy[v];
double gap = sqrt(dx*dx + dy*dy) - cr[u] - cr[v];
double w = max(0.0, gap);
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
printf("%.10f\n", dist[N+1]);
return 0;
}
Trace: 3 Circles
Start = (0, 0), End = (10, 0). Three circles:
| Circle | Center | Radius |
|---|---|---|
| A | (2, 0) | 1.5 |
| B | (5, 1) | 1.0 |
| C | (8, 0) | 1.5 |
Nodes: S=0, A=1, B=2, C=3, E=4.
Edge weight computation:
| From | To | Center dist | r_i + r_j | Gap = max(0, dist - sum) |
|---|---|---|---|---|
| S | A | 2.00 | 1.50 | 0.50 |
| S | B | 5.10 | 1.00 | 4.10 |
| S | C | 8.00 | 1.50 | 6.50 |
| S | E | 10.00 | 0.00 | 10.00 |
| A | B | 3.16 | 2.50 | 0.66 |
| A | C | 6.00 | 3.00 | 3.00 |
| A | E | 8.00 | 1.50 | 6.50 |
| B | C | 3.16 | 2.50 | 0.66 |
| B | E | 5.10 | 1.00 | 4.10 |
| C | E | 2.00 | 1.50 | 0.50 |
Dijkstra trace:
| Step | Pop | dist[pop] | Updates | Best dist[] so far |
|---|---|---|---|---|
| 1 | S | 0.00 | A=0.50, B=4.10, C=6.50, E=10.00 | S=0, A=0.50, B=4.10, C=6.50, E=10.00 |
| 2 | A | 0.50 | B=min(4.10, 1.16)=1.16, C=min(6.50, 3.50)=3.50, E=min(10.00, 7.00)=7.00 | B=1.16, C=3.50, E=7.00 |
| 3 | B | 1.16 | C=min(3.50, 1.82)=1.82, E=min(7.00, 5.26)=5.26 | C=1.82, E=5.26 |
| 4 | C | 1.82 | E=min(5.26, 2.32)=2.32 | E=2.32 |
| 5 | E | 2.32 | — | done |
Answer: 2.32. Path: S -> A -> B -> C -> E. Total exposure = 0.50 + 0.66 + 0.66 + 0.50 = 2.32.
Direct S -> E would cost 10.00. The circles act as free highways.
Problem: ABC257-D Jumping Takahashi 2
There are \(N\) trampolines on a plane. Trampoline \(i\) is at \((x_i, y_i)\) with power \(P_i\). With training strength \(S\), you can jump from trampoline \(i\) to \(j\) if:
Find the minimum \(S\) such that there exists a trampoline from which you can reach all other trampolines.
Constraints: \(1 \le N \le 200\).
Binary Search on S
This is a parametric graph problem (covered more deeply in Lesson 5). For a fixed \(S\), build a directed graph: edge \(i \to j\) exists if \(P_i \times S \ge \text{dist}(i, j)\). Check if any node can reach all others via BFS/DFS.
But there's a slicker approach. For each pair \((i, j)\), the minimum \(S\) enabling edge \(i \to j\) is:
Build a complete directed graph with these edge weights. For each starting node, the answer is the maximum edge weight along the cheapest "reach-all" path — the bottleneck shortest path. Run a modified Dijkstra that minimizes the maximum edge weight.
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<long long> x(N), y(N), p(N);
for (int i = 0; i < N; i++)
cin >> x[i] >> y[i] >> p[i];
// cost[i][j] = min S to enable edge i -> j
vector<vector<long long>> cost(N, vector<long long>(N));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
long long d = abs(x[i]-x[j]) + abs(y[i]-y[j]);
cost[i][j] = (d + p[i] - 1) / p[i]; // ceil division
}
long long ans = LLONG_MAX;
// For each starting node, find min-bottleneck to reach all
for (int s = 0; s < N; s++) {
// Dijkstra minimizing max edge weight
vector<long long> best(N, LLONG_MAX);
priority_queue<pair<long long,int>,
vector<pair<long long,int>>,
greater<>> pq;
best[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > best[u]) continue;
for (int v = 0; v < N; v++) {
long long nd = max(d, cost[u][v]);
if (nd < best[v]) {
best[v] = nd;
pq.push({nd, v});
}
}
}
long long need = *max_element(best.begin(), best.end());
ans = min(ans, need);
}
cout << ans << endl;
return 0;
}
⚠ Gotcha. The graph is directed. Trampoline \(i\) with power 100 can reach faraway \(j\), but \(j\) with power 1 might not reach \(i\). Don't assume symmetry.
The Pattern
Geometric implicit graphs follow a template:
- Objects become nodes. Points, circles, rectangles, trampolines — each is a node.
- Proximity becomes edges. Define "connected" based on distance, overlap, or reachability. Compute the edge weight from the geometry.
- Build and solve. With \(N \le 1000\), a complete graph with \(O(N^2)\) edges is usually fine. Run Dijkstra, BFS, or MST.
The critical step is step 2: deciding what "connected" means. The problem never tells you. You infer it from the cost structure.
When Complete Graphs Are Too Large
For \(N > 10^4\), an \(O(N^2)\) complete graph won't fit. Techniques for sparse geometric graphs:
- Delaunay triangulation reduces to \(O(N)\) edges for MST-type problems.
- K-d trees prune distance queries.
- Grid bucketing groups nearby points.
But for contest problems with \(N \le 1000\), the complete graph is almost always the right approach. Don't over-optimize.
Common Mistakes
Integer vs. floating-point distances. Cosmic Rays uses Euclidean distance (floating point). Jumping Takahashi uses Manhattan distance (integer). Mixing them up causes subtle bugs.
Forgetting to include start/end as nodes. In Cosmic Rays, you need \(N + 2\) nodes, not \(N\). The start and end points are circles with radius 0.
Ignoring circle overlaps. If two circles overlap, the gap is 0, not negative. Always clamp with max(0, ...). A negative weight would break Dijkstra.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ARC064-C Cosmic Rays | atcoder.jp/contests/arc064/tasks/arc064_c | Medium |
| ABC257-D Jumping Takahashi 2 | atcoder.jp/contests/abc257/tasks/abc257_d | Medium |