Guest User

Untitled

a guest
Feb 14th, 2016
250
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vll;
  8. int inf_int=2e9;
  9. ll inf_ll=2e18;
  10. typedef pair<int,int> pii;
  11. #define pb push_back
  12. const double pi=3.1415926535898;
  13. #define dout if(debug) cout
  14. #define fi first
  15. #define se second
  16. #define sp setprecision
  17. #define sz size()
  18. #define x1 gfgs
  19. #define y1 asd
  20. bool debug=0;
  21.  
  22. int x[1010],y[1010],r[1010];
  23. bool used[1010],clo[1010];
  24. vector<int> g[1010];
  25. int rat[1010][10010];
  26. ll nod(ll x,ll y)
  27. {
  28. if(y==0)
  29. {
  30. return x;
  31. }
  32. return nod(y,x%y);
  33. }
  34. void solve()
  35. {
  36. int n;
  37. cin >> n;
  38. for(int i=0;i<n;i++)
  39. {
  40. cin >> x[i]>>y[i]>>r[i];
  41. }
  42. for(int i=0;i<n;i++)
  43. {
  44. for(int e=i+1;e<n;e++)
  45. {
  46. if((x[i]-x[e])*(x[i]-x[e])+(y[i]-y[e])*(y[i]-y[e])==(r[i]+r[e])*(r[i]+r[e]))
  47. {
  48. g[i].pb(e);
  49. g[e].pb(i);
  50. }
  51. }
  52. }
  53. vector<int> pr;
  54. pr.pb(2);
  55. for(int i=3;i<=1e4;i++)
  56. {
  57. bool k=1;
  58. for(int e=0;pr[e]*pr[e]<=i;e++)
  59. {
  60. if(i%pr[e]==0)
  61. {
  62. k=0;
  63. break;
  64. }
  65. }
  66. if(k)
  67. {
  68. pr.pb(i);
  69. }
  70. }
  71. queue<int> q;
  72. q.push(0);
  73. used[0]=1;
  74. clo[0]=1;
  75. rat[0][1]=1;
  76. while(!q.empty())
  77. {
  78. int v=q.front();
  79. q.pop();
  80. for(int i=0;i<g[v].sz;i++)
  81. {
  82. int to=g[v][i];
  83. if(used[to])
  84. {
  85. if(clo[to]==clo[v])
  86. {
  87. cout << -1;
  88. return;
  89. }
  90. }
  91. else
  92. {
  93. clo[to]=!clo[v];
  94. used[to]=1;
  95. q.push(to);
  96. ll x=r[v],y=r[to];
  97. ll nd=nod(x,y);
  98. x=x/nd;
  99. y=y/nd;
  100. for(int e=0;e<=10000;e++)
  101. {
  102. rat[to][e]=rat[v][e];
  103. }
  104.  
  105. for(int e=0;pr[e]*pr[e]<=x;e++)
  106. {
  107. while(x%pr[e]==0)
  108. {
  109. rat[to][pr[e]]++;
  110. x=x/pr[e];
  111. }
  112.  
  113. }
  114. for(int e=0;pr[e]*pr[e]<=y;e++)
  115. {
  116. while(y%pr[e]==0)
  117. {
  118. rat[to][pr[e]]--;
  119. y=y/pr[e];
  120. }
  121.  
  122. }
  123. rat[to][x]++;
  124. rat[to][y]--;
  125.  
  126. }
  127. }
  128. }
  129. if(!used[n-1])
  130. {
  131. cout << 0;
  132. return;
  133. }
  134.  
  135. ll ans1=1,ans2=1;
  136. for(int i=0;i<=1e4;i++)
  137. {
  138. if(rat[0][i]>=rat[n-1][i])
  139. {
  140. rat[0][i]=rat[0][i]-rat[n-1][i];
  141. rat[n-1][i]=0;
  142. }
  143. else
  144. {
  145. rat[n-1][i]=abs(rat[0][i]-rat[n-1][i]);
  146. rat[0][i]=0;
  147. }
  148. while(rat[0][i])
  149. {
  150. ans1=ans1*i;
  151. rat[0][i]--;
  152. }
  153. while(rat[n-1][i])
  154. {
  155. ans2=ans2*i;
  156. rat[n-1][i]--;
  157. }
  158.  
  159. }
  160.  
  161.  
  162. if(clo[0]==clo[n-1])
  163. {
  164. cout << ans1<<" "<<ans2;
  165. }
  166. else
  167. {
  168. cout << ans1<<" "<<-ans2;
  169. }
  170.  
  171. }
  172.  
  173. #define FILE "humble"
  174. int main()
  175. {
  176.  
  177. // freopen("input.txt","r",stdin);
  178. // freopen("output.txt","w",stdout);
  179.  
  180. // freopen(FILE".in","r",stdin);
  181. // freopen(FILE".out","w",stdout);
  182. if(!debug)
  183. {
  184. ios_base::sync_with_stdio(0);
  185. cin.tie(0);
  186. cout.tie(0);
  187. }
  188. int t=1;
  189. while(t--)
  190. solve();
  191. return 0;
  192. }
RAW Paste Data