We are given $$$n$$$ points $$$(x_i, y_i)$$$, each with a transmission radius $$$r_i$$$. If a point already has the signal, it will transmit the signal to another point if:
or
Once a point receives the signal, it will also start transmitting according to the same rule.
Task: Find the minimum number of points that must be directly connected to the signal so that, starting from these initially connected points, all $$$n$$$ points will eventually receive the signal.
Constraints
Example:
3
1 0 1
2 0 1
5 0 1
Output:
2
Please help me with this problem, thank you very much.
Auto comment: topic has been updated by bao987 (previous revision, new revision, compare).
what's the goal of this post , is it for finding solution / suggesting good problem / or discussing better solution than present one. It's not specified so I'll think of it as suggesting a good problem to fellows. I'm thinking about using graphs (don't know how but will try :) )
Oh, sorry, I completely forgot to mention what I need. Right now, I don’t know how to solve this problem yet. I’m guessing it might be related to geometry or sweepline, but I don’t have a concrete approach. I’d like everyone’s help — do you have any ideas for a solution?
Yeah , i think your idea is right.I guess this problem is counting connected components since the graph is undirected.I guess your problem is that you can't build this graph,right?(cause n is too large)
Yes, exactly. So I need some ideas from everyone — maybe a sweep line?
Feels similar to this.
Problem 2. WiFi Stations (7 points)
Alice is designing a wired internet connection system for WiFi stations. Specifically, on the coordinate plane there are n WiFi stations, numbered from 1 to n. The i-th station (1 ≤ i ≤ n) has coordinates (xi, yi).
In order for a station to broadcast internet, Alice must connect it to the internet via a cable to one station. If station i already has internet, it can broadcast within a radius of ri, and any station within that radius will also have internet. That station can in turn continue to broadcast within its own radius, and so on…
More precisely, if a station with coordinates (x, y) and radius r has internet, then any station with coordinates (u, v) such that (x – u)² + (y – v)² ≤ r² will also have internet.
Alice wants to connect cables to as few stations as possible so that all n stations can broadcast internet.
Requirement: Given the coordinates and radii of the stations, help Alice determine the minimum number of stations that need to be connected via cables so that all n stations can broadcast internet.
Input: (from the file WIFI.INP)
The first line contains a positive integer n (n ≤ 2 × 10^5), the number of stations.
Each of the next n lines contains three integers xi, yi, ri (|xi|, |yi| ≤ 10^6; 0 < ri ≤ 10^6). Note: There may be multiple stations at the same location.
Output: (to the file WIFI.OUT)
Output a single positive integer — the minimum number of stations that need to be connected via cables so that all n stations can broadcast internet.
Constraints:
Subtask 1 (20%): n ≤ 10
Subtask 2 (20%): n ≤ 1000
Subtask 3 (20%): All stations’ coordinates lie on the same straight line
Subtask 4 (20%): ri ≤ 10
Subtask 5 (20%): No additional constraints
This is the full problem statement that I’m asking about. Perhaps the problem you suggested to me and this one are two completely different problems.
They are different problems, but a similar trick can be used to solve it.
Is it true that they really share the same trick? Thank you.