http://acm.pku.edu.cn/JudgeOnline/problem?id=3643
这题的正解应该是枚举a, b然后用半平面交求解.
但是看了别人的代码长度, 我就立刻放弃的这种做法.
事实上, 这题可以用迭代的方法不断逼近解.
假设s = a * xi + b * yi + c * zi + d;
要使s从小于0变成大于等于0, 只需要使a = a + x[i], b = b + y[i], c = c + z[i], d = d + 1, 使不等式满足要求为止.
虽然可以不断逼近解, 但是不能估算出究竟需要多少步才能得到解, 所以这个只是一种近似解法.
/**
* @version 2009/08/24
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_N = 400;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int[] x = new int[MAX_N], y = new int[MAX_N], z = new int[MAX_N];
private static int N, M, size;
public static void main(String[] argv) throws Exception {
while ((N = nextInt()) >= 0) {
readIn();
solve();
}
}
private static void readIn() throws Exception {
int i;
for (i = 0; i < N; i++) {
x[i] = nextInt();
y[i] = nextInt();
z[i] = nextInt();
}
M = nextInt();
size = N + M;
for (i = N; i < size; i++) {
x[i] = nextInt();
y[i] = nextInt();
z[i] = nextInt();
}
}
private static void solve() {
double a = 0.0, b = 0.0, c = 0.0, d = 0.0;
int i, j;
boolean refresh = true;
for (i = 2 * M * N; refresh && i > 0; i--) {
refresh = false;
for (j = 0; j < N; j++) {
if (a * x[j] + b * y[j] + c * z[j] + d > 0) {
a -= x[j];
b -= y[j];
c -= z[j];
d--;
refresh = true;
}
}
for (j = N; j < size; j++) {
if (a * x[j] + b * y[j] + c * z[j] + d <= 0) {
a += x[j];
b += y[j];
c += z[j];
d++;
refresh = true;
}
}
}
System.out.println(a + " " + b + " " + c + " " + d);
}
private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return Integer.parseInt(st.nextToken());
}
}