Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iomanip>
- #include <iostream>
- #include <map>
- #include <set>
- #include <string>
- #include <queue>
- #include <tuple>
- #include <vector>
- using namespace std;
- const int START_COLOR = 0;
- const int COLOR1 = 1;
- const int COLOR2 = -1;
- void Dfs(int idx, const vector<int>& x_coords, const vector<int>& y_coords, int dist,
- vector<int>& colors, bool& is_bipartite, int color)
- {
- colors[idx] = COLOR1;
- for (int i = 0; i < idx; ++i) {
- if (i == idx) continue;
- if ((x_coords[i] - x_coords[idx]) * (x_coords[i] - x_coords[idx]) +
- (y_coords[i] - y_coords[idx]) * (y_coords[i] - y_coords[idx]) > dist) continue;
- if (colors[i] == START_COLOR) {
- Dfs(i, x_coords, y_coords, dist, colors, is_bipartite, -color);
- } else if (colors[i] != -color) {
- is_bipartite = false;
- return;
- }
- }
- }
- bool IsBipartite(const vector<int>& x_coords, const vector<int>& y_coords, int dist) {
- vector<int> colors(x_coords.size(), START_COLOR);
- bool is_bipartite = true;
- for (int i = 0; i < x_coords.size(); ++i) {
- if (colors[i] != START_COLOR) continue;
- Dfs(i, x_coords, y_coords, dist, colors, is_bipartite, COLOR1);
- }
- return is_bipartite;
- }
- int main() {
- int stations_count;
- cin >> stations_count;
- vector<int> x_coords(stations_count);
- vector<int> y_coords(stations_count);
- for (int i = 0; i < stations_count; ++i) {
- cin >> x_coords[i] >> y_coords[i];
- }
- int64_t l = 0;
- int64_t r = 2 * (10'000 + 10'000) * (10'000 + 10'000) + 1;
- while (l + 1 < r) {
- int64_t m = (l + r) / 2;
- if (IsBipartite(x_coords, y_coords, m)) l = m;
- else r = m;
- }
- cout << fixed << setprecision(8) << sqrt(l) / 2;
- return 0;
- }
- /*
- test1
- 4
- 0 0
- 0 1
- 1 0
- 1 1
- 0.70710678118654752
- 1 2 2 1
- */
Advertisement
Add Comment
Please, Sign In to add comment