待补充
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.BitSet; public class Main { public static class Edge implements Comparable { int len; int a, b;//端点 public Edge(int a, int b) { this.a = a; this.b = b; this.len = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]); } @Override public int compareTo(Object o) { return ((Edge)o).len - this.len; } } static int[] x = new int[3010]; static int[] y = new int[3010]; static Edge[] edges = new Edge[4500000]; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(bf.readLine()); for(int i = 0; i < n; ++i) { String[] strs = bf.readLine().split(" "); x[i] = Integer.parseInt(strs[0]); y[i] = Integer.parseInt(strs[1]); } int nums = 0; for(int i = 0; i < n; ++i) { for(int j = i + 1; j < n; ++j) { edges[nums++] = new Edge(i, j); } } Arrays.sort(edges, 0, nums); BitSet[] bitSets = new BitSet[n]; for(int i = 0; i < n; ++i) { bitSets[i] = new BitSet(3010); } for(int i = 0; i < nums; ++i) { BitSet tmp = (BitSet) bitSets[edges[i].a].clone(); tmp.and(bitSets[edges[i].b]); if(tmp.cardinality() != 0) { System.out.printf("%.20f\n", Math.sqrt(edges[i].len) / 2.0); break; } else { bitSets[edges[i].a].set(edges[i].b, true); bitSets[edges[i].b].set(edges[i].a, true); } } } }
链接:https://www.luogu.com.cn/problem/CF333E
来源:洛谷