Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:66777216")
- #define _USE_MATH_DEFINES
- #define _CRT_SECURE_NO_WARNINGS
- #include <algorithm>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <utility>
- #include <map>
- #include <set>
- #include <iostream>
- #include <sstream>
- #include <iomanip>
- #include <memory.h>
- #include <assert.h>
- #include <list>
- #include <deque>
- #include <stack>
- #include <bitset>
- #include <functional>
- #include <numeric>
- #include <cmath>
- #include <ctime>
- #include <queue>
- #pragma hdrstop
- using namespace std;
- #define pb push_back
- #define mp make_pair
- #define X first
- #define Y second
- #define y0 __MY_Y0__
- #define y1 __MY_Y1__
- #define yn __MY_YN__
- #define sz(a) (int)a.size()
- #define fill(a, x) memset (a, x, sizeof(a))
- #ifdef _DEBUG
- #define Eo(x) {cout << "# " << #x << " = " << (x) << endl;}
- #define E(x) {cout << "# " << #x << " = " << (x) << " ";}
- #define Ou(x) {cout << "# " << (x) << endl;}
- #define OK {cout << "# OK Line : " << __LINE__ << endl;}
- #else
- #define Eo(x)
- #define E(x)
- #define Ou(x)
- #define OK
- #endif
- #ifdef WIN32
- #define LLD "%I64d"
- #else
- #define LLD "%lld"
- #endif
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int, int> pii;
- inline void sIO() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- #endif
- }
- inline void iIO() {freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);}
- inline void fIO(string fn) {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin); freopen ("output.txt", "w", stdout);
- #else
- freopen((fn + ".in").c_str(), "r", stdin); freopen((fn + ".out").c_str(), "w", stdout);
- #endif
- }
- inline void TM() {
- #ifdef _DEBUG
- cout << endl << "# Time: " << clock() / 1000. << endl;
- #endif
- }
- inline void swap(short& a, short& b) {b ^= a ^= b ^= a;}
- inline void swap(int& a, int& b) {b ^= a ^= b ^= a;}
- inline void swap(char& a, char& b) {b ^= a ^= b ^= a;}
- inline void swap(ll& a, ll& b) {b ^= a ^= b ^= a;}
- template<class T> inline T abs(T x) {return x < 0 ? -x : x;}
- template<class T> inline T sqr(T x) {return x * x;}
- template<class T> inline T min(T& a, T& b) {return a < b ? a : b;}
- template<class T> inline T max(T& a, T& b) {return a > b ? a : b;}
- 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;}
- template<class T> inline T lcm(T a, T b) {return a / gcd(a, b) * b;}
- 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;}
- template<class T> inline string toa(T x) {stringstream ss; ss << x; string ret; ss >> ret; return ret;}
- 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;}
- 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;}
- inline int toi(string s) {stringstream ss; ss << s; int ret; ss >> ret; return ret;}
- inline ll tol(string s) {stringstream ss; ss << s; ll ret; ss >> ret; return ret;}
- inline int Random() {return ((rand() << 16) | rand());}
- inline char upperCase(char ch) {return (ch >= 'a' && ch <= 'z') ? ch^32 : ch;}
- inline char lowerCase(char ch) {return (ch >= 'A' && ch <= 'Z') ? ch^32 : ch;}
- 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;}
- 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;}
- inline int dig(char ch) {return ch - 48;}
- inline bool isAlpha(char ch) {return (ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z');}
- inline bool isDigit(char ch) {return (ch >= '0' && ch <= '9');}
- inline bool isLowerCase(char ch) {return (ch >= 'a' && ch <= 'z');}
- inline bool isUpperCase(char ch) {return (ch >= 'A' && ch <= 'Z');}
- int __;
- const int INF = 0x3f3f3f3f;
- const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
- const long double EPS = 1e-12;
- const int MD = 1000000007;
- int n, pnt[555], cx;
- pii p[555];
- pair<long double, int> a[555][555];
- long double ans[555], mx, mn, v, dv;
- bool w[555];
- long double root3(long double x) {
- return exp(log(x) / 3);
- }
- long double pow3(long double x) {
- return x * x * x;
- }
- int main() {
- fIO("soapbubbles");
- scanf("%d%Lf%Lf", &n, &v, &dv);
- mx = v / dv;
- for (int i = 0; i < n; ++i)
- scanf("%d%d", &p[i].X, &p[i].Y);
- fill(w, 1);
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j)
- 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);
- sort(a[i], a[i] + n);
- pnt[i] = 1;
- }
- for (int i = 0; i < n; ++i)
- for (int j = i + 1; j < n; ++j)
- assert(p[i].X != p[j].X || p[i].Y != p[j].Y);
- #if 0
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j)
- printf("%.6lf=%d ", a[i][j].X, a[i][j].Y);
- cout << endl;
- }
- #endif
- for (int i = 0; i < n; ++i) {
- mn = 1e9;
- cx = -1;
- for (int j = 0; j < n; ++j)
- if (w[j]) {
- while (pnt[j] < n && a[j][pnt[j]].X < mx + EPS && !w[a[j][pnt[j]].Y]) ++pnt[j];
- if (pnt[j] == n || a[j][pnt[j]].X > mx + EPS) {
- w[j] = false;
- ans[j] = mx;
- } else
- if (a[j][pnt[j]].X + EPS < mn) {
- mn = a[j][pnt[j]].X;
- cx = j;
- }
- }
- if (cx < 0) {
- for (int j = 0; j < n; ++j)
- if (w[j]) ans[j] = mx;
- break;
- }
- w[cx] = w[a[cx][pnt[cx]].Y] = false;
- ans[cx] = ans[a[cx][pnt[cx]].Y] = mn;
- }
- for (int i = 0; i < n; ++i)
- printf("%.16Lf ", ans[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement