fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) begin(x), end(x)
  4. #define int int64_t
  5.  
  6. using namespace std;
  7.  
  8. typedef double ftype;
  9. typedef complex<ftype> point;
  10. #define x real
  11. #define y imag
  12.  
  13. const ftype pi = acos(-1);
  14. const ftype inf = 1e16;
  15. const ftype eps = 1e-6;
  16.  
  17. ftype dot(point a, point b) {
  18. 	return a.x() * b.x() + a.y() * b.y();
  19. }
  20. ftype cross(point a, point b) {
  21. 	return a.x() * b.y() - a.y() * b.x();
  22. }
  23.  
  24. void read(point &r) {
  25. 	ftype x, y;
  26. 	cin >> x >> y;
  27. 	r = {x, y};
  28. }
  29.  
  30. ftype area(ftype r, ftype a) {
  31. 	return norm(r) * acos(a / r) - a * sqrt(norm(r) - norm(a));
  32. }
  33.  
  34. ftype overlap(ftype r1, ftype r2, ftype d) {
  35. 	if(d >= r1 + r2) {
  36. 		return 0;
  37. 	} else if(d <= abs(r1 - r2)) {
  38. 		return pi * norm(min(r1, r2));
  39. 	} else {
  40. 		ftype a = (norm(r1) - norm(r2) + norm(d)) / (2 * d); 
  41. 		return area(r1, a) + area(r2, d - a);
  42. 	}
  43. }
  44.  
  45. ftype sign(ftype x) {
  46. 	return x < 0 ? -1 : 1;
  47. }
  48. tuple<point, point, ftype> reflect(point A, point Av, ftype Ar, point W1, point W2) {
  49. 	point nrm = point(0, 1) * (W2 - W1);
  50. 	nrm /= abs(nrm);
  51. 	ftype d = dot(A - W1, nrm);
  52. 	ftype Vd = dot(Av, nrm);
  53. 	point A_ = A - 2 * (d - sign(d) * Ar) * nrm;
  54. 	point Av_ = Av - 2 * Vd * nrm;
  55. 	if(abs(Vd) < eps || sign(d - sign(d) * Ar) == sign(Vd)) {
  56. 		return {A, Av, 0};
  57. 	} else {
  58. 		ftype At = -(d - sign(d) * Ar) / Vd;
  59. 		return {A_, Av_, At};
  60. 	}
  61. }
  62.  
  63. ftype dist(point A, point Av, point B, point Bv, ftype tl, ftype tr) {
  64. 	if(tl > tr) {
  65. 		return inf;
  66. 	} else {
  67. 		Bv -= Av;
  68. 		ftype t = dot(A - B, Bv) / norm(Bv);
  69. 		if(tl <= t && t <= tr) {
  70. 			return abs(cross(A - B, Bv)) / abs(Bv);
  71. 		} else {
  72. 			return min(abs(A - (B + tl * Bv)), abs(A - (B + tr * Bv)));
  73. 		}
  74. 	}
  75. }
  76.  
  77. void solve() {
  78. 	point A, Av; ftype Ar;
  79. 	point B, Bv; ftype Br;
  80. 	read(A); read(Av); cin >> Ar;
  81. 	read(B); read(Bv); cin >> Br;
  82. 	point W1, W2;
  83. 	read(W1); read(W2);
  84. 	point A_, Av_, B_, Bv_;
  85. 	ftype At, Bt;
  86. 	tie(A_, Av_, At) = reflect(A, Av, Ar, W1, W2);
  87. 	tie(B_, Bv_, Bt) = reflect(B, Bv, Br, W1, W2);
  88. 	ftype d = min({dist(A, Av, B, Bv, 0, min(At, Bt)), 
  89. 		           dist(A_, Av_, B, Bv, At, Bt),
  90. 		           dist(A, Av, B_, Bv_, Bt, At),
  91. 		           dist(A_, Av_, B_, Bv_, max(At, Bt), inf)});
  92. 	cout << overlap(Ar, Br, d) << "\n";
  93. }
  94.  
  95. signed main() {
  96. 	//freopen("input.txt", "r", stdin);
  97. 	ios::sync_with_stdio(0);
  98. 	cin.tie(0);
  99. 	cout << fixed << setprecision(12);
  100. 	int t;
  101. 	cin >> t;
  102. 	while(t--) {
  103. 		solve();
  104. 	}
  105. 	return 0;
  106. }
  107.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BxTHwO
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!