4.6平面上的分治法（1）
挑战程序竞赛系列（61）：4.6平面上的分治法（1）
思路： 分治，参考《挑战》P365：
alt text
alt text
利用分治后左平面和右平面的最小d来限制第二种情况的查询，绝了。关于第二种情形的算法采用平面扫描法，但前提y需要排序。
注意一些细节：比如如何确定矩形y的范围，先来看看代码：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/U0245.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 10000 + 16;
static final double INF = 1e4;
class Pair implements Comparable<Pair>{
double x;
double y;
Pair(double x, double y){
this.x = x;
this.y = y;
}
@Override
public String toString() {
return x + " " + y;
}
@Override
public int compareTo(Pair that) {
if (this.x != that.x) return Double.compare(this.x, that.x);
return Double.compare(this.y, that.y);
}
}
Pair[] tmp = new Pair[MAX_N];
double solve(Pair[] p, int l, int r) {
if (r - l <= 1) return 12341234;
int mid = (l + r) / 2;
double x = p[mid].x;
double d = Math.min(solve(p, l, mid), solve(p, mid, r));
int k = 0;
int ll = l, rr = mid;
while (ll < mid && rr < r) {
if (p[ll].y < p[rr].y) tmp[k++] = p[ll++];
else tmp[k++] = p[rr++];
}
while (ll < mid) tmp[k++] = p[ll++];
while (rr < r) tmp[k++] = p[rr++];
for (int i = l; i < r; ++i) p[i] = tmp[i - l];
// for (int i = l, j = mid, k = l; k < r;) {
// if (j >= r || i < mid && p[i].y < p[j].y) tmp[k++] = p[i++];
// else tmp[k++] = p[j++];
// }
// for (int i = l; i < r; ++i) p[i] = tmp[i];
List<Pair> b = new ArrayList<>();
for (int i = l; i < r; ++i) {
if (Math.abs(p[i].x - x) >= d) continue;
for (int j = b.size() - 1; j >= 0; --j) {
double dx = p[i].x - b.get(j).x;
double dy = p[i].y - b.get(j).y;
if (Math.abs(dy) >= d) break;
d = Math.min(d, Math.sqrt(dx * dx + dy * dy));
}
b.add(p[i]);
}
return d;
}
void read() {
while (true) {
int N = ni();
if (N == 0) break;
Pair[] points = new Pair[N];
for (int i = 0; i < N; ++i) {
double x = nd();
double y = nd();
points[i] = new Pair(x, y);
}
Arrays.sort(points);
double ans = solve(points, 0, N);
if (ans >= INF) out.println("INFINITY");
else {
out.printf("%.4f\n", ans);
}
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
read();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}此处：
List<Pair> b = new ArrayList<>();
for (int i = l; i < r; ++i) {
if (Math.abs(p[i].x - x) >= d) continue;
for (int j = b.size() - 1; j >= 0; --j) {
double dx = p[i].x - b.get(j).x;
double dy = p[i].y - b.get(j).y;
if (Math.abs(dy) >= d) break;
d = Math.min(d, Math.sqrt(dx * dx + dy * dy));
}
b.add(p[i]);
}纠结了很久，注意第二个循环的break，使用break，说明dy >= d的情况都不需要比较，那么必须满足当前点和之前最大的那些点进行比较，continue的话，就与顺序无关，因为遍历了所有情况，但估计数据量一大就超时，根据书上的定义该for循环不会超过6次，可以认为是常数级的。
alt text
POJ 3714: Raid
求能量站和人之间的最短顶点对。
思路： 多了个限制，人与能量站之间的最短距离，那么在分治求解时，当且仅当遇到两个顶点分别是人和能量站时进行最短距更新即可。
代码如下：
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P3714.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 100000 + 16;
static final int INF = 0x3f3f3f3f;
class Pair implements Comparable<Pair>{
double x;
double y;
boolean man;
Pair(double x, double y, boolean man){
this.x = x;
this.y = y;
this.man = man;
}
@Override
public String toString() {
return x + " " + y;
}
@Override
public int compareTo(Pair o) {
return x > o.x ? -1 : 1;
}
}
Pair[] tmp = new Pair[2 * MAX_N];
double solve(Pair[] p, int l, int r) {
if (r - l <= 1) return INF;
int m = (l + r) / 2;
double x = p[m].x;
double d = Math.min(solve(p, l, m), solve(p, m, r));
// merge
for (int i = l, j = m, k = l; k < r;) {
if (j >= r || i < m && p[i].y < p[j].y) tmp[k++] = p[i++];
else tmp[k++] = p[j++];
}
for (int i = l; i < r; ++i) p[i] = tmp[i];
List<Pair> b = new ArrayList<Pair>();
for (int i = l; i < r; ++i) {
if (Math.abs(p[i].x - x) >= d) continue;
for (int j = b.size() - 1; j >= 0; --j) {
double dx = p[i].x - b.get(j).x;
double dy = p[i].y - b.get(j).y;
if (p[i].man ^ b.get(j).man) {
if (Math.abs(dy) >= d) break;
d = Math.min(d, Math.sqrt(dx * dx + dy * dy));
}
}
b.add(p[i]);
}
return d;
}
void read() {
int T = ni();
while (T --> 0) {
int N = ni();
Pair[] points = new Pair[2 * N];
for (int i = 0; i < N; ++i) {
points[i] = new Pair(nd(), nd(), false);
}
for (int i = 0; i < N; ++i) {
points[i + N] = new Pair(nd(), nd(), true);
}
Arrays.sort(points);
out.printf("%.3f\n", solve(points, 0, 2 * N));
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
read();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}
alt text
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年09月13日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录