#include using namespace std; typedef long long ll; typedef long double ld; struct pt{ typedef pt P; ll x, y; explicit pt(ll x=0, ll y=0) : x(x), y(y) {} // y then x comparison bool operator<(P p) const { return tie(y,x) < tie(p.y,p.x); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(int s) const { return P(s*x, s*y); } ll dot(P p) const { return x*p.x + y*p.y; } ll dot(P a, P b) const { return (a-*this).dot(b-*this); } ll cross(P p) const { return x*p.y - y*p.x; } ll cross(P a, P b) const { return (a-*this).cross(b-*this); } double angle() const { return atan2((double)y, (double)x); } ll dist2() const { return x*x + y*y; } ll dist2(P a) const { return (a-*this).dist2(); } }; ostream& operator<<(ostream &o,const pt &p) { return o<<"("< pol; pol chull(pol p) { sort(p.begin(), p.end()); int top=0, bot=1, n=p.size(); pol ch(2*n); for (int i = 0, d = 1; i < n && i >= 0; i += d) { // If no duplicates, can change <= 0 to < 0 to keep redundant points while (top>bot && (ch[top-1]-ch[top-2]).cross(p[i]-ch[top-2])<=0) top--; ch[top++] = p[i]; if (i == n-1) d = -1, bot = top; } ch.resize(max(1, top-1)); return ch; } int n, k, d; const int MAXN = 2001; ld choose[MAXN][MAXN]; ld chs(int n, int k) { if (n> n >> k >> d; vector pts; for(int i=0;i> x >> y; pts.emplace_back(round(x*100),round(y*100)); } double ans = d*M_PI; // events, +1 is insertion into halfplane, -1 is removal from halfplane for(int i=0;i> ids; for(int j=0;j ap, pair bp) { pt a = (pts[ap.first]-pts[i])*ap.second; pt b = (pts[bp.first]-pts[i])*bp.second; if (a.y >= 0 && b.y<0) return true; if (a.y < 0 && b.y>=0) return false; if (a.y ==0 && b.y ==0) { if (a.x > 0 && b.x < 0) return true; else if (a.x <0 && b.x > 0) return false; if (ap.second*bp.second == -1) return ap.second ==-1; return abs(a.x) < abs(b.x); } if (a.cross(b) == 0) { if (ap.second*bp.second == -1) return ap.second ==-1; return a.dist2() < b.dist2(); } return a.cross(b) > 0; }; // exact integer sorting sort(ids.begin(), ids.end(), cmp); // for(auto [a,b]: ids) cerr<< pts[a]-pts[i] << " " << b << endl;// cerr << endl; int j = 0; // initialize halfplane int left = 0; for(int steps=0;steps<2*(n-1);steps++,j=(j+1)%ids.size()) { int a = ids[j].first; int sa = ids[j].second; if ((pts[a]-pts[i]).y*sa < 0 || ((pts[a]-pts[i]).y==0 && (pts[a]-pts[i]).x*sa < 0)) break; if (sa==1) left++; } // sweep events starting from here. for(int steps=0;steps<2*(n-1);steps++, j=(j+1)%ids.size()) { int a = ids[j].first; int sa = ids[j].second; //cerr <