題意是三維空間上有一點集{a1,a2...an}，每個點 ai 有一個參數 pi，現在要找到一點 t
使得所有形如 （|t.x - ai.x| +|t.y - ai.y| + |t.z - ai.z|）/pi 的值最大的最小
b_merry的做法：
1 #include <string>
2 #include <vector>
3 #include <map>
4 #include <cstdlib>
5 #include <cstring>
6 #include <cassert>
7 #include <set>
8 #include <iostream>
9 #include <sstream>
10 #include <cstddef>
11 #include <algorithm>
12 #include <utility>
13 #include <iterator>
14 #include <numeric>
15 #include <list>
16 #include <complex>
17 #include <cstdio>
18
19 using namespace std;
20
21 typedef vector<int> vi;
22 typedef vector<string> vs;
23 typedef long long ll;
24 typedef complex<double> pnt;
25 typedef pair<int, int> pii;
26
27 #define RA(x) (x).begin(), (x).end()
28 #define FE(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
29 #define SZ(x) ((int) (x).size())
30
31 template<class T>
32 void splitstr(const string &s, vector<T> &out)
33 {
34 istringstream in(s);
35 out.clear();
36 copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
37 }
38
39 template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
40
41 struct ship
42 {
43 double xyz[3];
44 double p;
45 };
46
47 static bool reached(double q, const vector<ship> &ships)
48 {
49 /*如果要滿足最小的q，那ships必定散落在四面八方，否則就不是最小
50 這樣就有四個 關于x , y, z 的約束不等式 */
51 int delta[3][4] =
52 {
53 {1, 1, 1, 1},
54 {-1, -1, 1, 1},
55 {-1, 1, -1, 1}
56 };
57 int N = ships.size();
58 double range[4][2];
59 for (int i = 0; i < 4; i++)
60 {
61 range[i][0] = -HUGE_VAL;
62 range[i][1] = HUGE_VAL;
63 }
64 for (int i = 0; i < N; i++)
65 {
66 for (int a = 0; a < 4; a++)
67 {
68 double m =
69 delta[0][a] * ships[i].xyz[0]
70 + delta[1][a] * ships[i].xyz[1]
71 + delta[2][a] * ships[i].xyz[2];
72 range[a][0] = max(range[a][0], m - q * ships[i].p);
73 range[a][1] = min(range[a][1], m + q * ships[i].p);//求形如x * y * z的范圍，*代表加或減
74 }
75 }
76 for (int a = 0; a < 4; a++)
77 {
78 if (range[a][0] > range[a][1])
79 return false;
80 }
81
82 bool low = false, high = false;
83 for (int v = 0; v < 8; v++)
84 {
85 double x_y_z = (v & 1) ? range[0][1] : range[0][0]; // （x-y-z）的范圍
86 double x_yz = (v & 2) ? range[1][1] : range[1][0]; // (x -y+z)的范圍
87 double xy_z = (v & 4) ? range[2][1] : range[2][0];// (x+y-z)的范圍
88 /* 三個約束方程，又有三個未知數，所以單獨每個成立的話，他們就成立了，
89 這三個約束不等式，再并上第四個如果有交集，就說明存在繼續縮小的可能
90 */
91 double xyz = x_yz + xy_z - x_y_z; //（x+y+z）的范圍
92 if (xyz >= range[3][0] && xyz <= range[3][1])//第四個約束條件范圍更大
93 return true;
94 else if (xyz < range[3][0])
95 low = true;
96 else
97 high = true;
98 }
99 return low && high;//第四個約束條件范圍更小
100 }
101
102 int main()
103 {
104 int cases;
105 cin >> cases;
106 for (int cas = 0; cas < cases; cas++)
107 {
108 int N;
109 cin >> N;
110 vector<ship> ships(N);
111 for (int i = 0; i < N; i++)
112 cin >> ships[i].xyz[0]
113 >> ships[i].xyz[1]
114 >> ships[i].xyz[2]
115 >> ships[i].p;
116 double l = 0.0;
117 double r = 1e9;
118 while (r - l > 1e-8 && r - l > 1e-8 * r)
119 {
120 double m = (l + r) * 0.5;
121 if (reached(m, ships))
122 r = m;
123 else
124 l = m;
125 }
126 printf("Case #%d: %.9f\n", cas + 1, l);
127 }
128 return 0;
129 }
130
posted on 2009-03-08 16:00
wangzhihao 閱讀(187)
評論(0) 編輯 收藏 引用