Guest User

Untitled

a guest
Oct 27th, 2012
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.42 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <set>
  8. #include <memory.h>
  9. #include <map>
  10. #include <math.h>
  11. #include <queue>
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. #include <string>
  15. #include <iostream>
  16. #include <algorithm>
  17. #include <vector>
  18. #include <set>
  19. #include <memory.h>
  20. #include <map>
  21. #include <math.h>
  22. #include <queue>
  23. #include <stack>
  24. #include <complex>
  25. #include <list>
  26. #include <deque>
  27. #pragma comment(linker, "/STACK:16777216") // SET_STACKSIZE_16MB
  28. using namespace std;
  29.  
  30. #ifdef WIN32
  31.     #define LLD "%I64d"
  32. #else
  33.     #define LLD "%lld"
  34. #endif
  35.  
  36. typedef long long ll;
  37. typedef unsigned long long ull;
  38.  
  39. const long double PI = acos(-1.0);
  40. const double eps = 1e-12;
  41. const int INF = 2147483647;
  42. const ll LLINF = 9223372036854775807LL;
  43. const int MAXPRIMES = 3163; // 3163 = sqrt(10^9) (FOR GENPRIMES)
  44. const int MAXSIZESTR = 110; // FOR GEN_HASH
  45. const int BASE = 31;
  46. const ll MOD = 1000000073;
  47. const ll MAXN = 100010;
  48.  
  49. #define mp make_pair
  50. #define pb push_back
  51. #define sz(x) (int)x.size()
  52. #define X first
  53. #define Y second
  54. #define all(x) x.begin(),x.end()
  55. #define last(x) x[sz(x)-1]
  56.  
  57. //INTTOSTR,STRTOINT
  58. inline ll gcd(ll a, ll b){return b==0?a:gcd(b, a%b);}
  59. inline ll lcm(ll a, ll b){return a*b/gcd(a,b);}
  60. template<class T> inline T sqr(T x){return x*x;}    
  61. template<class T> inline T abs(T x) {return x < 0 ? -x : x;}
  62. //INTTOSTR,STRTOINT
  63. template<class T> string toStr(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}
  64. inline ll toLL(string s){ll r=0;istringstream sin(s);sin>>r;return r;}
  65. //WORK_WITH_CHAR
  66. inline bool isUpperCase(char c){return c>='A' && c<='Z';}
  67. inline bool isLowerCase(char c){return c>='a' && c<='z';}
  68. inline char toLowerCase(char c){return (isUpperCase(c))?(c+32):c;}
  69. inline char toUpperCase(char c){return (isLowerCase(c))?(c-32):c;}
  70. inline bool isLetter(char c){return c>='A' && c<='Z' || c>='a' && c<='z';}
  71. inline bool isDigit(char c){return c>='0' && c<='9';}
  72. //POWER,POWER % MOD
  73. inline ll ppow (ll a, ll b) {ll ret = 1; while (b) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
  74. 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;}
  75. //GEOMETRY
  76. int crossOper (double x0,double y0,double x1,double y1,double x2,double y2)
  77. {double t=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);if (fabs(t)<=eps) return 0;return (t<0)?-1:1;}
  78. bool isIntersect (double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
  79. {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;}
  80. long double distance (long double x1,long double y1,long double x2,long double y2){return sqrt(sqr(x1-x2)+sqr(y1-y2));}
  81. ll vect(ll x1, ll x2, ll y1, ll y2) {return x1*y2-x2*y1;}
  82. ll scal(ll x1, ll x2, ll y1, ll y2) {return x1*x2+y1*y2;}
  83. //LINE_AND_DOT (1 - LEFT; 0 - TOWARDS, BACKWARDS, ON LINE; -1 - RIGHT)
  84. 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);
  85. if(res==0)return 0;if(res<0) return 1;if(res>0)return -1;}
  86. // SQR_OF_TRIANGLE
  87. double sqrTriangle(double x1,double y1,double x2,double y2,double x3,double y3) {double m3m1X = x3 - x1;double m3m1Y = y3 - y1;
  88. double m3m2X = x3 - x2; double m3m2Y = y3 - y2; double res = abs(0.5*vect(m3m1X,m3m1Y,m3m2X,m3m2Y)); return res;}
  89. //GENERATE_PRIMES
  90. vector<int> genPrimes() {bool visit[MAXPRIMES+10]={false}; vector<int> primes;for (int i = 2; i <= MAXPRIMES; i++ )
  91. if (!visit[i]){primes.pb(i); for (int j = i * 2; j <= MAXPRIMES; j += i )visit[j] = 1;}return primes;}
  92. //FACTORIZATION (return divizor^power)
  93. 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)
  94. 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)
  95. if (sz(p)>0 &&  p[sz(p)-1].X == n) p[sz(p)-1].Y++; else p.pb(mp(n,1)); return p;}
  96. //RADIX (FROMDEC,TODEC)
  97. inline string fromDec(ll num,int base)
  98. {string s="";string d="!0123456789ABCDEF";do{s=d[(num%base)+1]+s;num/=base;}while(num!=0);return s;}
  99. inline ll toDec(string num,int base) {string d="!0123456789ABCDEF";ll m=0;int start=0;int pos=0;while(num[start]=='0')start++;
  100. 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;}
  101. //GENERATE_HASH
  102. void generateHash(string s, ll _hash[], ll _power[])
  103. {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;}}
  104. void generatePower(string s, ll _power[])
  105. {_power[0] = 1;for (size_t i = 1; i < sz(s); i++)_power[i] = (_power[i-1] * BASE) % MOD;}
  106. inline ll CountHash(int i, int len, int szS, ll _hash[], ll _power[])
  107. {ll cur_hash = _hash[i+len-1];if (i)  cur_hash -= _hash[i-1];if (cur_hash < 0) cur_hash += MOD;
  108. cur_hash *= _power[szS-i-1];cur_hash %= MOD;return cur_hash;}
  109. //END_TEAMPLATE
  110.  
  111. int n,Vmax,dV;
  112. pair< int, int > a[510];
  113. long double table[510][510];
  114. bool visited[510];
  115. long double answer[510];
  116. set<int> Crack;
  117.  
  118. int main()
  119. {
  120.     freopen("soapbubbles.in", "rt", stdin);
  121.     freopen("soapbubbles.out", "wt", stdout);
  122.     //freopen("input.txt", "r", stdin);
  123.     //freopen("output.txt", "w", stdout);
  124.     scanf("%d%d%d", &n, &Vmax, &dV);
  125.  
  126.     for (int i = 0; i < 510; i++)
  127.         visited[i] = false;
  128.  
  129.     for (int i = 0; i < n; i++)
  130.         scanf("%d%d", &a[i].X, &a[i].Y);
  131.  
  132.     long double tmax = Vmax / dV;
  133.  
  134.     for (int i = 0; i < n; i++)
  135.         for (int j = 0; j < n; j++)
  136.         {
  137.             if (i != j)
  138.             {
  139.                 long double radius = (distance(a[i].X,a[i].Y,a[j].X,a[j].Y))/2;
  140.                 long double newT = (4*PI*radius*radius*radius)/(dV*3);
  141.                 table[i][j] = newT;
  142.             }
  143.             else
  144.                 table[i][j] = tmax;
  145.         }
  146.  
  147.     int cnt = 0;
  148.     while (cnt < n)
  149.     {
  150.         long double min = LLINF;
  151.         Crack.clear();
  152.         for (int i = 0; i < n ; i++)
  153.             if (!visited[i])
  154.                 for (int j = 0; j < n; j++)
  155.                     if (!visited[j])
  156.                     {
  157.                         if (table[i][j] < min)
  158.                         {
  159.                             min = table[i][j];
  160.                             Crack.clear();
  161.                             Crack.insert(i);
  162.                             Crack.insert(j);
  163.                         }
  164.                         if (table[i][j] - min < eps)
  165.                         {
  166.                             Crack.insert(i);
  167.                             Crack.insert(j);
  168.                         }
  169.                     }
  170.         for (set<int>::iterator itr = Crack.begin(); itr != Crack.end(); itr++)
  171.         {
  172.             visited[*itr] = true;
  173.             answer[*itr] = min;
  174.         }
  175.         cnt += sz(Crack);
  176.     }
  177.  
  178.     for (int i = 0; i < n; i++)
  179.         printf("%0.12llf ", answer[i]);
  180.     return 0;
  181. }
Advertisement
Add Comment
Please, Sign In to add comment