Problem: Background

The kindergarten attached to the University of Aizu is a kindergarten where children who love programming gather. Yu, one of the kindergarten children, loves darts as much as programming. Yu-kun was addicted to darts recently, but he got tired of ordinary darts, so he decided to make his own darts board.

See darts for darts.

Problem

The contents of the darts that Yu-kun thought about are as follows.

The infinitely wide darts board has several polygons with scores. The player has only one darts arrow. The player throws an arrow and stabs the arrow into one of the polygons to get the score written there. If you stab it in any other way, you will not get any points.

Yu-kun decided where to throw the arrow, but it doesn't always stick exactly. The darts board is a two-dimensional plane, and the position Yu-kun is aiming for is a point (cx, cy). The place where the arrow thrown by Yu-kun sticks is selected with a uniform probability from any point included in the circle with radius r centered on the point (cx, cy). The coordinates of the exposed points do not have to be integers.

Since the information on the darts board, the position (cx, cy) that Yu-kun aims at, and the radius r are given, answer the expected value of the score that Yu-kun can get.

Constraints

The input satisfies the following conditions.

* All inputs are given as integers
* 1 ≤ n ≤ 50
* 0 ≤ cx, cy, x, y ≤ 1000
* 1 ≤ r ≤ 100
* 3 ≤ p ≤ 10
* 1 ≤ score ≤ 100
* Polygon vertices are given in such an order that they visit adjacent vertices clockwise or counterclockwise.
* The sides of a polygon do not have anything in common with the sides of another polygon
* A polygon does not contain another polygon
* If the arrow sticks on the side of the polygon, no score will be given.

Input


n cx cy r
Information on the 0th polygon
Information on the first polygon
...
Information on the (n-1) th polygon


n is the number of polygons on the darts board. Polygonal information is given in the following format.


p score
x0 y0
x1 y1
...
x (p-1) y (p-1)


p represents the number of vertices of the polygon, and score represents the score written on the polygon. Each line segment of the polygon is a line segment connecting the vertices of (xi, yi) and (xi + 1, yi + 1) (i <p-1), and (xp-1, yp-1) and (x0, It is a line segment connecting the vertices of y0).

Output

Output the expected value of the score that Yu-kun can get in one line. Any number of digits after the decimal point may be output. However, the error in the answer must not exceed 0.000001 (10-6).

Examples

Input

1 2 2 1
4 1
0 0
2 0
2 2
0 2


Output

0.2500000000


Input

1 2 2 1
4 1
0 0
5 0
5 5
0 5


Output

1.0000000000


Input

4 3 3 2
3 1
1 1
3 3
1 5
4 2
2 0
5 0
4 2
3 2
3 3
4 3
6 1
6 5
4 4
3 4
4 4
5 6
2 6


Output

1.0574955319


Input

1 10 10 1
4 10
0 0
1 0
1 1
0 1


Output

0.0000000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T>ostream&operator<<(ostream &o,const vector<T>&t){o<<'[';FOR(i,t){if(i!=t.begin())o<<',';o<<*i;}return o<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)output(a[i],i!=n-1?',':10);}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}

typedef complex<double> P;
P pIN() { double x,y; cin >> x >> y; return P(x,y); }
namespace std {
  bool operator<(const P& a, const P& b) {
    // if (abs(a-b)<EPS) return 0;
    return real(a)!=real(b) ? real(a)<real(b) : imag(a)<imag(b);
  }
  bool operator==(const P& a, const P &b) {return abs(a-b)<EPS;}
}
double det(const P& a, const P& b) {return imag(conj(a)*b);}
double dot(const P& a, const P& b) {return real(conj(a)*b);}
double sig(double r) {return r<-EPS?-1:r>EPS?1:0;}
int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (sig(det(b,c))) return sig(det(b,c));  
  if (dot(b, c) < -EPS) return +2; // c--a--b
  if (EPS < norm(b) && norm(b) < norm(c)-EPS) return -2; // a--b--c
  return 0;
}
class L {
  vector<P> v;
public:
  L(const P &a, const P &b) : v({a,b,b-a}) {}
  const P operator[](int i) const { return v[i]; }
  void sub(const P&p) { v[0] -= p; v[1] -= p; }
};
ostream &operator<<(ostream &os, const L &a) {
  return os << a[0] << " -> " << a[1];
}
typedef vector<P> G;
#define next(g,i) g[(i+1)%g.size()]
L line(const G &g, int i) {return L(g[i],g[(i+1)%g.size()]);}
struct C {
  P p; double r;
  C(const P &p, double r) : p(p), r(r) { }
};
bool iLL(const L &l, const L &m) {
  return sig(det(l[2], m[2])) || !sig(det(l[2], m[0]-l[0]));
}
bool iLS(const L &l, const L &s) {
  return det(l[2],s[0]-l[0]) * det(l[2],s[1]-l[0]) < EPS;
}
bool iLP(const L &l, const P &p) { return !sig(det(l[2], p-l[0])); }
bool iSS(const L &s, const L &t) {
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
         ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}
bool sameline(const L &s, const L &t) {
  return !sig(det(s[2],t[2])) && !sig(det(s[2],t[1]-s[0]));
}
bool onseg2(const L &s, const P &p) {return ccw(s[0],p,s[1]) == -2;}
bool different2(const L &l, const L &s) {
  return sig(det(l[2],s[0]-l[0])) * sig(det(l[2],s[1]-l[0])) == -1;
}
bool iSS2(const L &s, const L &t) {
  if (!sig(det(s[2],t[2]))) return onseg2(s,t[0]) || onseg2(s,t[1]) || onseg2(t,s[0]) || onseg2(t,s[1]);
  else return different2(s,t) && different2(t,s);
}
bool iSP(const L &s, const P &p) {
  return sig(norm(s[0]-p)+norm(s[1]-p)-norm(s[2])) <= 0;
};
bool iLH(const L &l, const L &h) {
  int s1 = sig(det(l[2],h[0]-l[0]));
  int s2 = sig(det(l[2],h[2]));
  return !s1 ? 1 : !s2 ? 0 : s1*s2<0;
}
bool iHS(const L &h, const L &s) {
  int c1 = ccw(h[0],h[1],s[0]);
  int c2 = ccw(h[0],h[1],s[1]);
  return iLH(s,h) && (c1*c2<=0 || c1==-2 || c2==-2);
}
// not verified
bool iHS2(const L &h, const L &s) {
  int c1 = ccw(h[0],h[1],s[0]);
  int c2 = ccw(h[0],h[1],s[1]);
  return iLH(s,h) && (c1*c2==-1 || (c1+c2 != 4 && !(c1&1) && !(c2&1)));
}
bool iHP(const L &h, const P &p) {
  if (!iLP(h,p)) return 0;
  return ccw(h[0],h[1],p) != 2;
}
bool iHH(const L &h, const L &k) { return iLH(h,k) && iLH(k,h); }
P crosspoint(const L &l, const L &m) {
  double A = det(l[2],m[2]);
  double B = det(l[2],l[1]-m[0]);
  if (!sig(A) && !sig(B)) return m[0];// same line
  if (!sig(A)) assert(0); // !!!PRECONDITION NOT SATISFIED!!!
  return m[0] + B/A*m[2];
}
P crosspoint2(const L &l, const L &m) { // 線分と線分の交点
  double A = det(l[2], m[2]);
  double B = det(l[2], l[1]-m[0]);
  if (!sig(A) && !sig(B)) { // same line
    if (iSP(l,m[0]) && iSP(l,m[1]))
      return 0.5*(m[0]+m[1]);
    if (iSP(m,l[0]) && iSP(m,l[1]))
      return 0.5*(l[0]+l[1]);
    REP(i,2) REP(j,2)
      if (iSP(l,m[i]) && iSP(m,l[j]))
        return 0.5*(m[i]+l[j]);
    return m[0];
  }
  if (!sig(A)) assert(0); // !!!PRECONDITION NOT SATISFIED!!!
  return m[0] + B / A * (m[1] - m[0]);
}

// 円c1が円c2を含むか判定
bool contain(const C &a, const C &b) {
  return abs(a.p - b.p) < a.r - b.r + EPS;
}
vector<L> tangentCP(const C &c, const P &p) {
  P v = c.p - p; double d = abs(v);
  if (d+EPS < c.r) return {};
  double l = sqrt(max(0.,d*d-c.r*c.r));
  return {L(p,p+v*P(l,c.r)/d), L(p,p+v*P(l,-c.r)/d)};
}
vector<L> tangentCC(const C &a, const C &b) {
  vector<L> ret;
  if (abs(a.p-b.p) - (a.r+b.r) > -EPS)
    ret = tangentCP(a, (a.p*b.r+b.p*a.r)/(a.r+b.r));
  if (sig(a.r-b.r)) {
    auto t = tangentCP(a, (-a.p*b.r+b.p*a.r)/(a.r-b.r));
    ret.insert(ret.end(), ALL(t));
  } else {
    P v = b.p - a.p;
    P u = v * P(0,a.r/abs(v));
    P q1 = a.p + u, q2 = a.p - u;
    ret.insert(ret.end(), {L(q1, q1+v), L(q2, q2+v)});
  }
  return ret;
}
vector<P> crosspointLC(const L &l, const C &c) {
  P v = l[1]-l[0];
  v /= abs(v);
  P o = l[0]+v*dot(c.p-l[0],v);
  double d = abs(o-c.p);
  if (c.r+EPS < d) return {};
  v *= sqrt(max(0.,c.r*c.r-d*d));
  return {o-v,o+v};
}
vector<P> crosspointSC(const L &s, const C &c) {
  vector<P> res, t = crosspointLC(s, c);
  FOR(it, t) if (iSP(s, *it)) res.push_back(*it);
   return res;
}
// 同一円は？
vector<P> crosspointCC(const C &a, const C &b) {
  P p = b.p-a.p;
  double d = abs(p);
  if (abs(a.r-b.r) > d + EPS) return {};
  double x = (d*d+a.r*a.r-b.r*b.r)/(2*d);
  P o = a.p+p/d*x;
  p *= P(0,sqrt(max(0., a.r*a.r-x*x))/d);
  return {o-p, o+p};  
}
// ベクトルａからみたベクトルｂの角度の[0,2pi)
double angle(const P &a, const P &b) {
  double ret = arg(b)-arg(a);
  if (!sig(ret)||!sig(ret-2*PI)) return 0;
  return ret>0 ? ret : ret + 2*PI;
}
// ベクトルaとベクトルbの間の角度
double angle2(const P &a, const P &b) {
  return min(angle(a,b), angle(b,a));
}
// ベクトルa,bで表される直線同士の間の角度
double angle3(const P &a, const P &b) {
  double r = abs(arg(b)-arg(a));
  if (r > PI) r -= PI;
  return r > PI/2 ? PI-r : r;
}
// 時計回り側は含み、半時計回り側は含まない
int quadrant(const P &a) {
  double x = real(a), y = imag(a);
  return x>0&&y>=0 ? 0 : x<=0&&y>0 ? 1 : x<0&&y<=0 ? 2 : 3;
}
// ロバストな角度比較
bool cmpAngle(const P &a, const P&b) { 
  int p = quadrant(a);
  int q = quadrant(b);
  return p!=q ? p<q : det(a,b)>0;
}
// ベクトルの回転
P rotate(P p, double ang) {
  return p * P(cos(ang), sin(ang));
}
// 原点周りの直線の回転
L rotate(L l, double ang) {
  return L(rotate(l[0], ang),rotate(l[1], ang));
}
struct AngleIntersection {
  typedef pair<double,double> pdd;
  vector<pdd> v;
  AngleIntersection() {
    v.push_back(pdd(0,2*PI));
  }
  double normalize(double a) {
    return fmod(fmod(a,2*PI)+2*PI,2*PI);
  }
  void update(double a, double b) {
    vector<pdd> t;
    a = normalize(a);
    b = normalize(b);
    if (a>b) {
      t.push_back(pdd(0,b));
      t.push_back(pdd(a,2*PI));
    } else {
      t.push_back(pdd(a,b));
    }
    vector<pdd> r;
    FOR(it, t) {
      FOR(jt, v) {
        double x1 = max(it->first,jt->first);
        double x2 = min(it->second,jt->second);
        if (x1<=x2) {
          r.push_back(pdd(x1,x2));
        }
      }
    }
    v = r;
  }
  bool ok() {
    FOR(it, v) {
      if (it->second-it->first>EPS) return 1;
    }
    return 0;
  }
};
struct AngleIntersection2 {
  typedef pair<P,int> Pi;
  vector<Pi> v;
  void add(const P &a, const P &b) {
    v.push_back(Pi(a*P(cos(EPS),sin(EPS)),1));
    v.push_back(Pi(b*P(cos(-EPS),sin(-EPS)),0));
  }
  bool ok() {
    sort(ALL(v), [](const Pi &a, const Pi &b) { return cmpAngle(a.first,b.first); });
    int cnt = 0;
    int n = v.size()/2;
    REP(i,v.size()*2) {
      if (v[i%v.size()].second) cnt++;
      else cnt = 0;
      if (cnt == n) return 1;
    }
    return 0;
  }
};

FILE *fp;
double scale = 30;
P diff(30, 30);
double WH = 500;
void outputLine(const L &l) {
  if (!fp) return;
  P a = l[0];
  P b = l[1];
  a = a*P(scale,0)+diff;
  b = b*P(scale,0)+diff;
  fprintf(fp,"line(%f,%f,%f,%f);\n",a.real(),WH-a.imag(),b.real(),WH-b.imag());  
}
void outputCircle(C c) {
  if (!fp) return;
  c.p = c.p*P(scale,0) + diff;
  c.r *= scale;
  fprintf(fp, "circle(%f,%f,%f);\n", c.p.real(), WH-c.p.imag(), c.r);
}
void outputG(const G &g) {
  if (!fp) return;
  REP(i,g.size()) {
    outputLine(L(g[i], g[(i+1)%g.size()]));
  }
}
// 三角形 (0,0) - p - q と 円((0,0),r) の共通部分の符号付き面積
double intersectAreaTriC(P p, P q, double r) {
  double res = 0;
  vector<P> v = crosspointSC(L(p,q),C(P(),r));
  // outputLine(L(p,q));
  // outputCircle(C(P(),r));
  // cout << p << "->" << q << " " << r << " " << crosspointLC(L(p,q), C(P(),r)) << " " << endl;
  // FOR(it, v) {
  //   outputCircle(C(*it,1));
  // }
  if (v.size() == 2) {
    res = abs(det(v[0],v[1])) + r*r*(angle2(p,q)-angle2(v[0],v[1]));
  } else if (v.size() == 1) {
    if (abs(p) > r) res += r*r*angle2(p,v[0]);
    else res += abs(det(p,v[0]));
    if (abs(q) > r) res += r*r*angle2(q,v[0]);
    else res += abs(det(q,v[0]));
  } else {
    res = min(r*r*angle2(p,q), abs(det(p,q)));
  }
  if (det(p,q) < 0) res = -res;
  return res / 2;
}
// 多角形と円の共通部分の面積
double intersectAreaGC(const G &g, const C &c) {
  double res = 0;
  REP(i,g.size()) {
    res += intersectAreaTriC(g[i]-c.p,next(g,i)-c.p,c.r);
  }
  return res;
}
// 円の共通部分の面積
double CircleCircleArea(double r1, double r2, double d) {
  if (r1+r2-d<EPS) return 0;
  if (r1 < r2) swap(r1,r2);
  if (r1-r2-d>-EPS || r2<EPS) return r2*r2*PI;
  double t1 = acos((d*d+r1*r1-r2*r2)/(2*d*r1));
  double t2 = acos((d*d+r2*r2-r1*r1)/(2*d*r2));
  double sq = (r1*r1*sin(t1*2) + r2*r2*sin(t2*2)) * 0.5;
  return r1*r1*t1 + r2*r2*t2 - sq;
}
// 最小包含円
C minimumCircle(const vector<P> &ps) {
  P g;
  FOR(it, ps) g += *it;
  g /= ps.size();
  double len = 2000000;
  P diff;
  REP(_,10000) {
    diff = P(0,0);
    FOR(it, ps) {
      P tmp = *it - g;
      if (norm(tmp) > norm(diff)) diff = tmp;
    }
    diff /= abs(diff);
    g += diff * len;
    len *= 0.98;
  }
  return C(g, abs(diff));
}

double area2(const G &g) {
  double A = 0;
  REP(i,g.size()) A += det(g[i], next(g,i));
  return A;
}


int main() {
  fp = fopen("data.js", "w");
  int n,cx,cy,r;
  while(input(n,cx,cy,r)) {
    double ans = 0;
    C c(P(cx,cy),r);
    outputCircle(c);
    double S = PI*r*r;
    REP(i,n) {
      int p,score;
      input(p,score);
      G g;
      REP(j,p) {
        g.push_back(pIN());
      }
      if (area2(g) < 0) {
        reverse(ALL(g));
      }
      outputG(g);
      double a = intersectAreaGC(g,c);
      // cout << a << endl;
      // cout << i << " " << a/S << " " << a << " " << area2(g)/2 << endl;
      ans += score * a / S;
    }
    printf("%.10f\n", ans);
  }
}