Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string>
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <memory.h>
- #include <map>
- #include <math.h>
- #include <queue>
- #include <stdio.h>
- #include <stdlib.h>
- #include <string>
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <memory.h>
- #include <map>
- #include <math.h>
- #include <queue>
- #include <stack>
- #include <complex>
- #include <list>
- #include <deque>
- #pragma comment(linker, "/STACK:16777216") // SET_STACKSIZE_16MB
- using namespace std;
- #ifdef WIN32
- #define LLD "%I64d"
- #else
- #define LLD "%lld"
- #endif
- typedef long long ll;
- typedef unsigned long long ull;
- const long double PI = acos(-1.0);
- const double eps = 1e-12;
- const int INF = 2147483647;
- const ll LLINF = 9223372036854775807LL;
- const int MAXPRIMES = 3163; // 3163 = sqrt(10^9) (FOR GENPRIMES)
- const int MAXSIZESTR = 110; // FOR GEN_HASH
- const int BASE = 31;
- const ll MOD = 1000000073;
- const ll MAXN = 100010;
- #define mp make_pair
- #define pb push_back
- #define sz(x) (int)x.size()
- #define X first
- #define Y second
- #define all(x) x.begin(),x.end()
- #define last(x) x[sz(x)-1]
- //INTTOSTR,STRTOINT
- inline ll gcd(ll a, ll b){return b==0?a:gcd(b, a%b);}
- inline ll lcm(ll a, ll b){return a*b/gcd(a,b);}
- template<class T> inline T sqr(T x){return x*x;}
- template<class T> inline T abs(T x) {return x < 0 ? -x : x;}
- //INTTOSTR,STRTOINT
- template<class T> string toStr(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}
- inline ll toLL(string s){ll r=0;istringstream sin(s);sin>>r;return r;}
- //WORK_WITH_CHAR
- inline bool isUpperCase(char c){return c>='A' && c<='Z';}
- inline bool isLowerCase(char c){return c>='a' && c<='z';}
- inline char toLowerCase(char c){return (isUpperCase(c))?(c+32):c;}
- inline char toUpperCase(char c){return (isLowerCase(c))?(c-32):c;}
- inline bool isLetter(char c){return c>='A' && c<='Z' || c>='a' && c<='z';}
- inline bool isDigit(char c){return c>='0' && c<='9';}
- //POWER,POWER % MOD
- inline ll ppow (ll a, ll b) {ll ret = 1; while (b) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
- inline ll ppow (ll a, ll b, ll md){ll ret=1;a%=md;while(b){if(b&1)ret=(ret*a)%md;a=a*a;a%=md;b>>=1;}return ret%md;}
- //GEOMETRY
- int crossOper (double x0,double y0,double x1,double y1,double x2,double y2)
- {double t=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);if (fabs(t)<=eps) return 0;return (t<0)?-1:1;}
- bool isIntersect (double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
- {return crossOper(x1,y1,x2,y2,x3,y3)*crossOper(x1,y1,x2,y2,x4,y4)<0 && crossOper(x3,y3,x4,y4,x1,y1)*crossOper(x3,y3,x4,y4,x2,y2)<0;}
- long double distance (long double x1,long double y1,long double x2,long double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}
- ll vect(ll x1, ll x2, ll y1, ll y2) {return x1*y2-x2*y1;}
- ll scal(ll x1, ll x2, ll y1, ll y2) {return x1*x2+y1*y2;}
- //LINE_AND_DOT (1 - LEFT; 0 - TOWARDS, BACKWARDS, ON LINE; -1 - RIGHT)
- int LineAndDot(double x1, double y1, double x2, double y2, double x3, double y3){double res=vect(x3-x1,x2-x1,y3-y1,y2-y1);
- if(res==0)return 0;if(res<0) return 1;if(res>0)return -1;}
- // SQR_OF_TRIANGLE
- double sqrTriangle(double x1,double y1,double x2,double y2,double x3,double y3) {double m3m1X = x3 - x1;double m3m1Y = y3 - y1;
- double m3m2X = x3 - x2; double m3m2Y = y3 - y2; double res = abs(0.5*vect(m3m1X,m3m1Y,m3m2X,m3m2Y)); return res;}
- //GENERATE_PRIMES
- vector<int> genPrimes() {bool visit[MAXPRIMES+10]={false}; vector<int> primes;for (int i = 2; i <= MAXPRIMES; i++ )
- if (!visit[i]){primes.pb(i); for (int j = i * 2; j <= MAXPRIMES; j += i )visit[j] = 1;}return primes;}
- //FACTORIZATION (return divizor^power)
- vector< pair<int, int> > factorization(int n) {int d = 2;vector< pair<int,int> > p;while (1){if (n%d==0){if (sz(p)>0 && p[sz(p)-1].X == d)
- p[sz(p)-1].Y++; else p.pb(mp(d,1));n /= d;} else d++; if (d > sqrt(n+0.)) break; if (n==1) break;} if (n != 1)
- if (sz(p)>0 && p[sz(p)-1].X == n) p[sz(p)-1].Y++; else p.pb(mp(n,1)); return p;}
- //RADIX (FROMDEC,TODEC)
- inline string fromDec(ll num,int base)
- {string s="";string d="!0123456789ABCDEF";do{s=d[(num%base)+1]+s;num/=base;}while(num!=0);return s;}
- inline ll toDec(string num,int base) {string d="!0123456789ABCDEF";ll m=0;int start=0;int pos=0;while(num[start]=='0')start++;
- for(int i=start;i<sz(num);i++){for(int j=0;j<sz(d);j++)if(d[j]==num[i]){pos=j;break;}m=m*base+pos-1;}return m;}
- //GENERATE_HASH
- void generateHash(string s, ll _hash[], ll _power[])
- {for (size_t i = 0; i < sz(s); i++){_hash[i] = (s[i] - 'a' + 1) * _power[i];if (i) _hash[i] += _hash[i-1];_hash[i] %= MOD;}}
- void generatePower(string s, ll _power[])
- {_power[0] = 1;for (size_t i = 1; i < sz(s); i++)_power[i] = (_power[i-1] * BASE) % MOD;}
- inline ll CountHash(int i, int len, int szS, ll _hash[], ll _power[])
- {ll cur_hash = _hash[i+len-1];if (i) cur_hash -= _hash[i-1];if (cur_hash < 0) cur_hash += MOD;
- cur_hash *= _power[szS-i-1];cur_hash %= MOD;return cur_hash;}
- //END_TEAMPLATE
- int n,Vmax,dV;
- pair< int, int > a[510];
- long double table[510][510];
- bool visited[510];
- long double answer[510];
- set<int> Crack;
- int main()
- {
- freopen("soapbubbles.in", "rt", stdin);
- freopen("soapbubbles.out", "wt", stdout);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- scanf("%d%d%d", &n, &Vmax, &dV);
- for (int i = 0; i < 510; i++)
- visited[i] = false;
- for (int i = 0; i < n; i++)
- scanf("%d%d", &a[i].X, &a[i].Y);
- long double tmax = Vmax / dV;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- {
- if (i != j)
- {
- long double radius = (distance(a[i].X,a[i].Y,a[j].X,a[j].Y))/2;
- long double newT = (4*PI*radius*radius*radius)/(dV*3);
- table[i][j] = newT;
- }
- else
- table[i][j] = tmax;
- }
- int cnt = 0;
- while (cnt < n)
- {
- long double min = LLINF;
- Crack.clear();
- for (int i = 0; i < n ; i++)
- if (!visited[i])
- for (int j = 0; j < n; j++)
- if (!visited[j])
- {
- if (table[i][j] < min)
- {
- min = table[i][j];
- Crack.clear();
- Crack.insert(i);
- Crack.insert(j);
- }
- if (table[i][j] - min < eps)
- {
- Crack.insert(i);
- Crack.insert(j);
- }
- }
- for (set<int>::iterator itr = Crack.begin(); itr != Crack.end(); itr++)
- {
- visited[*itr] = true;
- answer[*itr] = min;
- }
- cnt += sz(Crack);
- }
- for (int i = 0; i < n; i++)
- printf("%0.12llf ", answer[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment