Advertisement
Guest User

Untitled

a guest
Nov 17th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define db long double
  4. #define x first
  5. #define y second
  6. #define mp make_pair
  7. #define pb push_back
  8. #define all(a) a.begin(), a.end()
  9.  
  10. using namespace std;
  11.  
  12. const double EPS = 1e-8;
  13.  
  14. struct TVector {
  15. double x, y;
  16. };
  17.  
  18. TVector operator+(TVector a, TVector b) {
  19. return {a.x + b.x, a.y + b.y};
  20. }
  21.  
  22. TVector operator-(TVector a, TVector b) {
  23. return {a.x - b.x, a.y - b.y};
  24. }
  25.  
  26. double operator*(TVector a, TVector b) {
  27. return a.x * b.y - a.y * b.x;
  28. }
  29.  
  30. double operator%(TVector a, TVector b) {
  31. return a.x * b.x + a.y * b.y;
  32. }
  33.  
  34. TVector operator*(TVector a, double k) {
  35. return {a.x * k, a.y * k};
  36. }
  37.  
  38. double len(TVector a) {
  39. return sqrt(a % a);
  40. }
  41.  
  42. TVector norm(TVector a) {
  43. return a * (1. / len(a));
  44. }
  45.  
  46. struct TLine {
  47. double a, b, c;
  48. TLine(TVector A, TVector B) {
  49. a = A.y - B.y;
  50. b = B.x - A.x;
  51. c = A.y * B.x - B.y * A.x;
  52. }
  53. TLine(double a, double b, double c) : a(a), b(b), c(c) {}
  54. double dist(TVector A) {
  55. double top = abs(a * A.x + b * A.y - c);
  56. double bot = len({a, b});
  57. return top / bot;
  58. }
  59. };
  60.  
  61. vector <TVector> intersection(TLine l, TVector O, double r) {
  62. double d = l.dist(O);
  63. if (d > r + EPS) {
  64. return {};
  65. }
  66. TVector v = {-l.a, -l.b};
  67. TVector A = O + norm(v) * d;
  68. //cout << O.x << " " << r << " " << A.x << " " << A.y << endl;
  69. if (abs(r - d) < EPS) {
  70. return {A};
  71. }
  72. double len = sqrt(r * r - d * d);
  73. TVector u = norm({l.b, -l.a});
  74. return {A + u * len, A - u * len};
  75. }
  76.  
  77. vector <TVector> intersection(TVector O1, double r1, TVector O2, double r2) {
  78. double wasx = O1.x, wasy = O1.y;
  79. O2.x -= O1.x;
  80. O2.y -= O1.y;
  81. O1.x = 0;
  82. O1.y = 0;
  83. double a = 2 * O2.x;
  84. double b = 2 * O2.y;
  85. double c = (r1 * r1 - r2 * r2) + O2.x * O2.x + O2.y * O2.y;
  86. if (abs(a) < EPS && abs(b) < EPS) {
  87. return {};
  88. }
  89. TLine l(a, b, c);
  90. auto res = intersection(l, O2, r2);
  91. for (auto &t : res) {
  92. //cout << t.x << " " << t.y << "\n";
  93. t.x += wasx;
  94. t.y += wasy;
  95. }
  96. return res;
  97. }
  98.  
  99. vector<db> its(db x, db y, db r, db crd){
  100. if (fabsl(x-crd) - EPS > r) return {};
  101. db kek = r*r-(x*crd)*(x*crd);
  102. kek = max(kek, (db) 0);
  103. kek = sqrt(kek);
  104. return {y-kek, y+kek};
  105. }
  106.  
  107. vector<db> ginter(int x, int y, int r, int R, db crd){
  108. vector<db> a = its(x, y, r, crd);
  109. vector<db> b = its(x, y, R, crd);
  110. for (int i=0; i < b.size(); ++i) a.push_back(b[i]);
  111. sort(a.begin(), a.end());
  112. return a;
  113. }
  114.  
  115. db func(db x){
  116. return sqrt(1. - x*x) * x + asin(x);
  117. }
  118.  
  119. db integrate(db x, db y, db r, db xl, db xr, bool high){
  120. if (high){
  121. xl -= x, xr -= x;
  122. xl /= r, xr /= r;
  123. db delta = func(xr) - func(xl);
  124. delta *= (r*r);
  125. delta += (xr-xl) * y;
  126. return delta;
  127. }
  128. else{
  129. xl -= x, xr -= x;
  130. xl /= r, xr /= r;
  131. db delta = func(xr) - func(xl);
  132. delta *= (r*r);
  133. delta *= (-1);
  134. delta += (xr-xl) * y;
  135. return delta;
  136. }
  137. }
  138.  
  139. void solve(){
  140. int r, R, xa, ya, xb, yb;
  141. cin >> r >> R >> xa >> ya >> xb >> yb;
  142. xa += 200, ya += 200, xb += 200, yb += 200;
  143.  
  144. int lft = max(xa-R, xb-R);
  145. int rgt = min(xa+R, xb+R);
  146. if (lft >= rgt){
  147. cout << 0 << "\n";
  148. return;
  149. }
  150. vector<db> arr = {lft, rgt};
  151.  
  152. auto kek = intersection({xa, ya}, r, {xb, yb}, r);
  153. for (int i=0; i < kek.size(); ++i){
  154. db Q = kek[i].x;
  155. arr.push_back(Q);
  156. }
  157.  
  158. kek = intersection({xa, ya}, R, {xb, yb}, r);
  159. for (int i=0; i < kek.size(); ++i){
  160. db Q = kek[i].x;
  161. arr.push_back(Q);
  162. }
  163.  
  164. kek = intersection({xa, ya}, R, {xb, yb}, R);
  165. for (int i=0; i < kek.size(); ++i){
  166. db Q = kek[i].x;
  167. arr.push_back(Q);
  168. }
  169.  
  170. kek = intersection({xa, ya}, r, {xb, yb}, R);
  171. for (int i=0; i < kek.size(); ++i){
  172. db Q = kek[i].x;
  173. arr.push_back(Q);
  174. }
  175. sort(arr.begin(), arr.end());
  176.  
  177. db ans = 0;
  178.  
  179. for (int i=0; i + 1 < arr.size(); ++i){
  180. db F = arr[i], Q = arr[i+1];
  181. if (abs(Q-F) < EPS){
  182. continue;
  183. }
  184. db x = (Q+F)/2;
  185. vector<db> ainter = ginter(xa, ya, r, R, x);
  186. vector<db> binter = ginter(xb, yb, r, R, x);
  187.  
  188. vector<pair<db, int> > res;
  189. for (int j=0; j < ainter.size(); ++j) res.push_back({ainter[j], 1});
  190. for (int j=0; j < binter.size(); ++j) res.push_back({binter[j], 2});
  191. sort(res.begin(), res.end());
  192. int A = 0, B = 0;
  193. for (int j=0; j + 1 < res.size(); ++j){
  194. if (res[j].second==1) A++;
  195. else B++;
  196. if (A%2 != 0 && B % 2 != 0){
  197. if (res[j].second == 1){
  198. if (A==1) ans += integrate(xa, ya, R, A, B, 1);
  199. else ans += integrate(xa, ya, r, A, B, 0);
  200. }
  201. else{
  202. if (B==1) ans += integrate(xb, yb, R, A, B, 1);
  203. else ans += integrate(xb, yb, r, A, B, 0);
  204. }
  205. }
  206. else{
  207. if (res[j+1].second == 1){
  208. if (A==1) ans -= integrate(xa, ya, r, A, B, 1);
  209. else ans -= integrate(xa, ya, R, A, B, 0);
  210. }
  211. else{
  212. if (B==1) ans -= integrate(xb, yb, r, A, B, 1);
  213. else ans -= integrate(xb, yb, R, A, B, 0);
  214. }
  215. }
  216. }
  217.  
  218. }
  219.  
  220. cout.precision(10);
  221. cout << ans << "\n";
  222.  
  223. }
  224.  
  225. int main(){
  226. #ifdef LOCAL
  227. freopen("I_input.txt", "r", stdin);
  228. //freopen("I_output.txt", "w", stdout);
  229. #endif
  230. ios_base::sync_with_stdio(0);
  231. cin.tie(0);
  232. cout.precision(20);
  233.  
  234.  
  235. int t;
  236. cin >> t;
  237. for (int i=0; i < t; ++i) solve();
  238.  
  239. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement