#include using namespace std; typedef long long ll; typedef long double ld; struct pt{ typedef pt P; double x, y; explicit pt(double x=0, double 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); } double dot(P p) const { return x*p.x + y*p.y; } double dot(P a, P b) const { return (a-*this).dot(b-*this); } double cross(P p) const { return x*p.y - y*p.x; } double cross(P a, P b) const { return (a-*this).cross(b-*this); } double angle() const { return atan2(y, x); } double dist2() const { return x*x + y*y; } double 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; mt19937 rng(0x3ffff); for(int i=0;i> x >> y; x+=1e-12*((int)rng()%100000-50000); y+=1e-12*((int)rng()%100000-50000); pts.emplace_back(x,y); } double ans = d*M_PI; // events, +1 is insertion into halfplane, -1 is removal from halfplane for(int i=0;i ids; vector ang(2*n+1); for(int j=0;j0?1:-1) << " ang " <0?1:-1; 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 = abs(ids[j])-1; int sa =ids[j]>0?1:-1; // cerr <