Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <math.h>
- #include <bits/stdc++.h>
- using namespace std;
- #define FOR(i,a,b) for(int i=(a);i<(b);++i)
- #define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
- #define FILL(A,val) memset(A,val,sizeof(A))
- #define ITER(it,a) for(__typeof(a.begin()) it=a.begin();it!=a.end();++it)
- #define ALL(V) V.begin(),V.end()
- #define SZ(V) (int)V.size()
- #define PB push_back
- #define MP make_pair
- typedef long long LL;
- typedef unsigned long long ULL;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- const double PI = acos(-1.0);
- const int INF = 1000*1000*1000 + 7;
- const LL LINF = 1LL*INF*INF;
- struct Point
- {
- double x, y;
- };
- Point p[500], q[500];
- int n, N;
- double r;
- double ans = 0;
- bool cmp(Point p1, Point p2)
- {
- return atan2(p1.y,p1.x) < atan2(p2.y,p2.x);
- }
- void add_points(Point p1, Point p2)
- {
- double a = p2.y-p1.y;
- double b = p2.x - p1.x;
- double c = -a*p1.x-b*p1.y;
- double A, B, C, D;
- if (abs(b) > 1e-5)
- {
- A = 1 + a*a/b/b;
- B = -2*a*c/b/b;
- C = c*c/b/b-r*r;
- D = B*B - 4*A*C;
- cout <<D<<endl;
- Point p;
- p.x =(-B + sqrt(max(0.0,D)))/(2*A);
- p.y = sqrt(max(0.0,r*r-p.x*p.x));
- q[N++] = p;
- p.x = (-B - sqrt(max(0.0,D)))/(2*A);
- p.y = sqrt(max(0.0,r*r-p.x*p.x));
- q[N++] = p;
- }
- else
- {
- swap(a,b);
- A = 1 + a*a/b/b;
- B = -2*a*c/b/b;
- C = c*c/b/b-r*r;
- D = B*B - 4*A*C;
- Point p;
- p.y =(-B + sqrt(max(0.0,D)))/(2*A);
- p.x = sqrt(max(0.0,r*r-p.y*p.y));
- q[N++] = p;
- p.y = (-B - sqrt(max(0.0,D)))/(2*A);
- p.x = sqrt(max(0.0,r*r-p.y*p.y));
- q[N++] = p;
- }
- }
- double RES(double ang)
- {
- Point f;
- f.x = cos(ang)*r;
- f.y = sin(ang)*r;
- vector<double> qwe;
- FOR (i,0,n)
- qwe.PB(atan2(p[i].y-f.y,p[i].x-f.x));
- sort(qwe.begin(), qwe.end());
- FOR (i,0,n)
- {
- double m = qwe[i];
- double M = qwe[(i+1)%n] + (i+1 == n)*2*PI;
- if (M - m > PI) return 2*PI - (M-m);
- }
- return 0;
- }
- void tern(Point p1, Point p2)
- {
- double l = atan2(p1.y,p1.x), r = atan2(p2.y,p2.x);
- if (r < l + 1e-5) r += 2*PI;
- FOR (i,0,74)
- {
- double a1 = l + (r-l)/3, a2 = r + 2*(r-l)/3;
- if (RES(a1) > RES(a2)) r = a2;
- else l = a1;
- }
- ans = max(ans, RES(l));
- }
- int main()
- {
- freopen("in.txt","r",stdin);
- //ios::sync_with_stdio(false);cin.tie(0);
- cin >> n >> r;
- FOR (i,0,n)
- cin >> p[i].x >> p[i].y;
- FOR (i,0,n)
- add_points(p[i], p[(i+1)%n]);
- sort(q,q+N,cmp);
- FOR (i,0,N)
- {
- cout << q[i].x<< " "<<q[i].y<<endl;
- tern(q[i], q[(i+1)%N]);
- }
- printf("%.11lf\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement