Advertisement
agul

Untitled

Oct 27th, 2012
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.54 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:66777216")
  2. #define _USE_MATH_DEFINES
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #include <algorithm>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <utility>
  9. #include <map>
  10. #include <set>
  11. #include <iostream>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <memory.h>
  15. #include <assert.h>
  16. #include <list>
  17. #include <deque>
  18. #include <stack>
  19. #include <bitset>
  20. #include <functional>
  21. #include <numeric>
  22. #include <cmath>
  23. #include <ctime>
  24. #include <queue>
  25. #pragma hdrstop
  26.  
  27. using namespace std;
  28.  
  29. #define pb push_back
  30. #define mp make_pair
  31. #define X first
  32. #define Y second
  33. #define y0 __MY_Y0__
  34. #define y1 __MY_Y1__
  35. #define yn __MY_YN__
  36. #define sz(a) (int)a.size()
  37. #define fill(a, x) memset (a, x, sizeof(a))
  38.  
  39. #ifdef _DEBUG
  40. #define Eo(x) {cout << "# " << #x << " = " << (x) << endl;}
  41. #define E(x) {cout << "# " << #x << " = " << (x) << " ";}
  42. #define Ou(x) {cout << "# " << (x) << endl;}
  43. #define OK {cout << "# OK Line : " << __LINE__ << endl;}
  44. #else
  45. #define Eo(x)
  46. #define E(x)
  47. #define Ou(x)
  48. #define OK
  49. #endif
  50.  
  51. #ifdef WIN32
  52. #define LLD "%I64d"
  53. #else
  54. #define LLD "%lld"
  55. #endif
  56.  
  57. typedef long long ll;
  58. typedef unsigned long long ull;
  59. typedef pair<int, int> pii;
  60.  
  61. inline void sIO() {
  62. #ifdef _DEBUG
  63. freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  64. #endif
  65. }
  66. inline void iIO() {freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);}
  67. inline void fIO(string fn) {
  68. #ifdef _DEBUG
  69. freopen("input.txt", "r", stdin); freopen ("output.txt", "w", stdout);
  70. #else
  71. freopen((fn + ".in").c_str(), "r", stdin); freopen((fn + ".out").c_str(), "w", stdout);
  72. #endif
  73. }
  74. inline void TM() {
  75. #ifdef _DEBUG
  76. cout << endl << "# Time: " << clock() / 1000. << endl;
  77. #endif
  78. }
  79. inline void swap(short& a, short& b) {b ^= a ^= b ^= a;}
  80. inline void swap(int& a, int& b) {b ^= a ^= b ^= a;}
  81. inline void swap(char& a, char& b) {b ^= a ^= b ^= a;}
  82. inline void swap(ll& a, ll& b) {b ^= a ^= b ^= a;}
  83. template<class T> inline T abs(T x) {return x < 0 ? -x : x;}
  84. template<class T> inline T sqr(T x) {return x * x;}
  85. template<class T> inline T min(T& a, T& b) {return a < b ? a : b;}
  86. template<class T> inline T max(T& a, T& b) {return a > b ? a : b;}
  87. template<class T> inline T gcd(T a, T b) {if (a < b) swap(a, b); while (b) {a %= b; swap(a, b);} return a;}
  88. template<class T> inline T lcm(T a, T b) {return a / gcd(a, b) * b;}
  89. template<class T> inline bool isPrime(T n) {if (n < 2) return false; T kk = (T)sqrt(n + 0.); for (T i = 2; i <= kk; ++i) if (!(n % i)) return false; return true;}
  90. template<class T> inline string toa(T x) {stringstream ss; ss << x; string ret; ss >> ret; return ret;}
  91. template<class T> inline T ppow(T a, ll b) {T ret = 1; while (b) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
  92. template<class T> inline T ppow(T a, ll b, ll md) {T ret = 1; a %= md; while (b) {if (b & 1) ret = ret * a % md; a = a * a % md; b >>= 1;} return ret % md;}
  93. inline int toi(string s) {stringstream ss; ss << s; int ret; ss >> ret; return ret;}
  94. inline ll tol(string s) {stringstream ss; ss << s; ll ret; ss >> ret; return ret;}
  95. inline int Random() {return ((rand() << 16) | rand());}
  96. inline char upperCase(char ch) {return (ch >= 'a' && ch <= 'z') ? ch^32 : ch;}
  97. inline char lowerCase(char ch) {return (ch >= 'A' && ch <= 'Z') ? ch^32 : ch;}
  98. inline string upperCase(string s) {int ls = s.length(); for (int i = 0; i < ls; ++i) if (s[i] >= 'a' && s[i] <= 'z') s[i] ^= 32; return s;}
  99. inline string lowerCase(string s) {int ls = s.length(); for (int i = 0; i < ls; ++i) if (s[i] >= 'A' && s[i] <= 'Z') s[i] ^= 32; return s;}
  100. inline int dig(char ch) {return ch - 48;}
  101. inline bool isAlpha(char ch) {return (ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z');}
  102. inline bool isDigit(char ch) {return (ch >= '0' && ch <= '9');}
  103. inline bool isLowerCase(char ch) {return (ch >= 'a' && ch <= 'z');}
  104. inline bool isUpperCase(char ch) {return (ch >= 'A' && ch <= 'Z');}
  105.  
  106. int __;
  107.  
  108. const int INF = 0x3f3f3f3f;
  109. const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
  110. const long double EPS = 1e-12;
  111. const int MD = 1000000007;
  112.  
  113. int n, pnt[555], cx;
  114. pii p[555];
  115. pair<long double, int> a[555][555];
  116. long double ans[555], mx, mn, v, dv;
  117. bool w[555];
  118.  
  119. long double root3(long double x) {
  120. return exp(log(x) / 3);
  121. }
  122.  
  123. long double pow3(long double x) {
  124. return x * x * x;
  125. }
  126.  
  127. int main() {
  128. fIO("soapbubbles");
  129. scanf("%d%Lf%Lf", &n, &v, &dv);
  130. mx = v / dv;
  131. for (int i = 0; i < n; ++i)
  132. scanf("%d%d", &p[i].X, &p[i].Y);
  133. fill(w, 1);
  134. for (int i = 0; i < n; ++i) {
  135. for (int j = 0; j < n; ++j)
  136. a[i][j] = mp(pow3(sqrt(sqr(p[i].X - p[j].X) + sqr(p[i].Y - p[j].Y) + 0.) / 2) * 4 / 3 * M_PI / dv, j);
  137. sort(a[i], a[i] + n);
  138. pnt[i] = 1;
  139. }
  140. for (int i = 0; i < n; ++i)
  141. for (int j = i + 1; j < n; ++j)
  142. assert(p[i].X != p[j].X || p[i].Y != p[j].Y);
  143. #if 0
  144. for (int i = 0; i < n; ++i) {
  145. for (int j = 0; j < n; ++j)
  146. printf("%.6lf=%d ", a[i][j].X, a[i][j].Y);
  147. cout << endl;
  148. }
  149. #endif
  150. for (int i = 0; i < n; ++i) {
  151. mn = 1e9;
  152. cx = -1;
  153. for (int j = 0; j < n; ++j)
  154. if (w[j]) {
  155. while (pnt[j] < n && a[j][pnt[j]].X < mx + EPS && !w[a[j][pnt[j]].Y]) ++pnt[j];
  156. if (pnt[j] == n || a[j][pnt[j]].X > mx + EPS) {
  157. w[j] = false;
  158. ans[j] = mx;
  159. } else
  160. if (a[j][pnt[j]].X + EPS < mn) {
  161. mn = a[j][pnt[j]].X;
  162. cx = j;
  163. }
  164. }
  165. if (cx < 0) {
  166. for (int j = 0; j < n; ++j)
  167. if (w[j]) ans[j] = mx;
  168. break;
  169. }
  170. w[cx] = w[a[cx][pnt[cx]].Y] = false;
  171. ans[cx] = ans[a[cx][pnt[cx]].Y] = mn;
  172. }
  173. for (int i = 0; i < n; ++i)
  174. printf("%.16Lf ", ans[i]);
  175. return 0;
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement