Advertisement
Guest User

Untitled

a guest
Sep 30th, 2016
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7.  
  8. #define FOR(i,a,b) for(int i=(a);i<(b);++i)
  9. #define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
  10. #define FILL(A,val) memset(A,val,sizeof(A))
  11. #define ITER(it,a) for(__typeof(a.begin()) it=a.begin();it!=a.end();++it)
  12.  
  13. #define ALL(V) V.begin(),V.end()
  14. #define SZ(V) (int)V.size()
  15. #define PB push_back
  16. #define MP make_pair
  17.  
  18. typedef long long LL;
  19. typedef unsigned long long ULL;
  20. typedef vector<int> VI;
  21. typedef pair<int, int> PII;
  22.  
  23. const double PI = acos(-1.0);
  24. const int INF = 1000*1000*1000 + 7;
  25. const LL LINF = 1LL*INF*INF;
  26.  
  27. struct Point
  28. {
  29. double x, y;
  30. };
  31. Point p[500], q[500];
  32. int n, N;
  33. double r;
  34. double ans = 0;
  35.  
  36. bool cmp(Point p1, Point p2)
  37. {
  38. return atan2(p1.y,p1.x) < atan2(p2.y,p2.x);
  39. }
  40.  
  41. void add_points(Point p1, Point p2)
  42. {
  43. double a = p2.y-p1.y;
  44. double b = p2.x - p1.x;
  45. double c = -a*p1.x-b*p1.y;
  46. double A, B, C, D;
  47.  
  48. if (abs(b) > 1e-5)
  49. {
  50. A = 1 + a*a/b/b;
  51. B = -2*a*c/b/b;
  52. C = c*c/b/b-r*r;
  53. D = B*B - 4*A*C;
  54. cout <<D<<endl;
  55. Point p;
  56. p.x =(-B + sqrt(max(0.0,D)))/(2*A);
  57. p.y = sqrt(max(0.0,r*r-p.x*p.x));
  58. q[N++] = p;
  59.  
  60. p.x = (-B - sqrt(max(0.0,D)))/(2*A);
  61. p.y = sqrt(max(0.0,r*r-p.x*p.x));
  62. q[N++] = p;
  63. }
  64. else
  65. {
  66. swap(a,b);
  67. A = 1 + a*a/b/b;
  68. B = -2*a*c/b/b;
  69. C = c*c/b/b-r*r;
  70. D = B*B - 4*A*C;
  71.  
  72. Point p;
  73. p.y =(-B + sqrt(max(0.0,D)))/(2*A);
  74. p.x = sqrt(max(0.0,r*r-p.y*p.y));
  75. q[N++] = p;
  76.  
  77. p.y = (-B - sqrt(max(0.0,D)))/(2*A);
  78. p.x = sqrt(max(0.0,r*r-p.y*p.y));
  79. q[N++] = p;
  80. }
  81. }
  82.  
  83. double RES(double ang)
  84. {
  85. Point f;
  86. f.x = cos(ang)*r;
  87. f.y = sin(ang)*r;
  88. vector<double> qwe;
  89. FOR (i,0,n)
  90. qwe.PB(atan2(p[i].y-f.y,p[i].x-f.x));
  91. sort(qwe.begin(), qwe.end());
  92. FOR (i,0,n)
  93. {
  94. double m = qwe[i];
  95. double M = qwe[(i+1)%n] + (i+1 == n)*2*PI;
  96. if (M - m > PI) return 2*PI - (M-m);
  97. }
  98. return 0;
  99. }
  100.  
  101. void tern(Point p1, Point p2)
  102. {
  103. double l = atan2(p1.y,p1.x), r = atan2(p2.y,p2.x);
  104. if (r < l + 1e-5) r += 2*PI;
  105. FOR (i,0,74)
  106. {
  107. double a1 = l + (r-l)/3, a2 = r + 2*(r-l)/3;
  108. if (RES(a1) > RES(a2)) r = a2;
  109. else l = a1;
  110. }
  111. ans = max(ans, RES(l));
  112. }
  113.  
  114. int main()
  115. {
  116. freopen("in.txt","r",stdin);
  117. //ios::sync_with_stdio(false);cin.tie(0);
  118.  
  119. cin >> n >> r;
  120. FOR (i,0,n)
  121. cin >> p[i].x >> p[i].y;
  122. FOR (i,0,n)
  123. add_points(p[i], p[(i+1)%n]);
  124. sort(q,q+N,cmp);
  125. FOR (i,0,N)
  126. {
  127. cout << q[i].x<< " "<<q[i].y<<endl;
  128. tern(q[i], q[(i+1)%N]);
  129. }
  130. printf("%.11lf\n", ans);
  131. return 0;
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement