Noli turbare circulos meos!: 2015

মঙ্গলবার, ১০ নভেম্বর, ২০১৫

UVA 11639 Guard The Land

Easy Peasy :-D

Problem id : uva 11639

Code :

/****************************************
Cat Got Bored

*****************************************/

#include <bits/stdc++.h>



#define FOR(i, s, e) for(int i=s; i<e; i++) //excluding end point

#define loop(i, n) for(int i=0; i<n; i++) //n times

#define loop(n)  for(int i=0;i<n;i++) // n times

#define getint(n) scanf("%d", &n)

#define gi(n) scanf("%d",&n) //getint short form

#define pb(a) push_back(a)

#define sqr(x) (x)*(x)

#define CIN ios_base::sync_with_stdio(0); cin.tie(0);

#define ll long long int

#define ull unsigned long long int

#define dd double
#define d double

#define SZ(a) int(a.size())

#define read() freopen("input.txt", "r", stdin)

#define write() freopen("output.txt", "w", stdout)

#define mem(a, v) memset(a, v, sizeof(a))

#define ms(a,b) memset(a, b, sizeof(a))

#define all(v) v.begin(), v.end()

#define pi acos(-1.0)

#define pf printf

#define sf scanf

#define mp make_pair

#define paii pair<int, int>

#define padd pair<dd, dd>

#define pall pair<ll, ll>

#define fr first

#define sc second

#define getlong(n) scanf("%lld",&n)

#define gl(n) scanf("%lld",&n)

#define CASE(n) printf("Case %d: ",++n)

#define inf 1000000000   //10e9

#define EPS 1e-9


int area(int x1,int y1,int x2,int y2)
{
    return (x2-x1)*(y2-y1);
}
int main()
{
int night_no;
cin>>night_no;
int nt = 0;
while(night_no--)
{


int g1_llx,g1_lly,g1_urx,g1_ury;//ll == lower left // ur = upper right //g1 = guard 1
int g2_llx,g2_lly,g2_urx,g2_ury;

cin>>g1_llx>>g1_lly>>g1_urx>>g1_ury;
cin>>g2_llx>>g2_lly>>g2_urx>>g2_ury;
int ll_x_max = max(g1_llx,g2_llx);
int ll_y_max = max(g1_lly,g2_lly);
int ur_x_min = min(g1_urx,g2_urx);
int ur_y_min = min(g1_ury,g2_ury);

    int strong_sec_ar =0;

    if(ur_x_min > ll_x_max)
        if(ur_y_min > ll_y_max)
    {
        strong_sec_ar = (ur_x_min - ll_x_max)*(ur_y_min - ll_y_max);
    }
    int weak_sec_ar = area(g1_llx,g1_lly,g1_urx,g1_ury)
    + area(g2_llx,g2_lly,g2_urx,g2_ury) ;

    weak_sec_ar -= 2*strong_sec_ar;

    int not_sec_ar = 100*100;
    not_sec_ar -= weak_sec_ar + strong_sec_ar ;

    printf("Night %d: %d %d %d\n",++nt,strong_sec_ar,weak_sec_ar,not_sec_ar);


}


    return 0;
}

বুধবার, ২৮ অক্টোবর, ২০১৫

[Convex Hull] LightOJ 1239 - Convex Fence

Problem id : LOJ 1239

Think in terms of the trivial cases first.For n = 2 ,

For n = 3 ,

Can you guess the formula now?
l1 = dist(point 1,point 3)
l2 = dist(point 2,point 3)
l3 = dist(point 1,point 2)

And we can easily show that arc 1 + arc 2 + arc 3 make 360 degrees and as they are from the same circle .
The answer is sumof(li) + 2*PI*d

For n > 3 ,

So,the idea is to construct a convex hull from the points and find it's perimeter and add 2*PI*d to the answer , and done :-D

Code :

// Implementation of Andrew's monotone chain 2D convex hull algorithm.
// Asymptotic complexity: O(n log n).
// Practical performance: 0.5-1.0 seconds for n=1000000 on a 1GHz machine.
#include<bits/stdc++.h>
using namespace std;
#define PI acos(-1.0) // important constant; alternative #define PI (2.0 * acos(0.0))
typedef double coord_t;         // coordinate type
typedef double coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2

struct Point
{
    coord_t x, y;

    Point()
    {
        this->x = 0.0000000f;
        this->y = 0.0000000f;
    }
    Point(coord_t x,coord_t y)
    {

        this->x = x;
        this->y = y;

    }
    bool operator <(const Point &p) const
    {
        return x < p.x || (x == p.x && y < p.y);
    }

};
vector<Point>H_global;
double dist(Point p1, Point p2)                  // Euclidean distance
{
    // hypot(dx, dy) returns sqrt(dx * dx + dy * dy)
    return hypot(p1.x - p2.x, p1.y - p2.y);
}

// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const Point &O, const Point &A, const Point &B)
{
    return (long)(A.x - O.x) * (B.y - O.y) - (long)(A.y - O.y) * (B.x - O.x);
}

// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
void convex_hull(vector<Point> P)
{
    int n = P.size(), k = 0;
    vector<Point> H(2*n);

    // Sort points lexicographically
    sort(P.begin(), P.end());

    // Build lower hull
    for (int i = 0; i < n; ++i)
    {
        while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    // Build upper hull
    for (int i = n-2, t = k+1; i >= 0; i--)
    {
        while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    H.resize(k);
    for(int a=0; a<H.size(); a++)
        H_global.push_back(H[a]);


}
/*
//Implementation details
vector<Point>in;
Point p(-3.4,50);
Point p1(33.4,51);
Point p2(30.4,15);
Point p3(31.4,45);
Point p4(3.4,55);
Point p5(-33.4,15);
Point p6(-31.4,75);
in.push_back(p);
in.push_back(p1);
in.push_back(p2);
in.push_back(p3);
in.push_back(p4);
in.push_back(p5);
in.push_back(p6);

vector<Point>out = convex_hull(in);

for(int a=0;a<out.size();a++)
{
    Point pp = out[a];
    cout<<pp.x<<"  "<<pp.y<<endl;

}


*/
vector<Point>in;


int main()
{
    int T;
    int cas =0;
    scanf("%d",&T);
    while(T--)
    {
        int n,d;
        scanf("%d %d",&n,&d);
        while(n--)
        {
            coord_t x,y;
            cin>>x>>y;
            Point p(x,y);
            in.push_back(p);


        }

        convex_hull(in);
        vector<Point>    out_c_h(H_global.begin(),H_global.end());
        long double dist_sum = 0.000000000f;
        if(n==2)
        {
            dist_sum += 2*dist(in[0],in[1]);
        }
        else
            for(int a=0; a<out_c_h.size() - 1; a++)
            {
                dist_sum += dist(out_c_h[a],out_c_h[a+1]) ;
            }
        dist_sum += 2*PI*d;
        printf("Case %d: %Lf\n",++cas,dist_sum);
        out_c_h.clear();
        in.clear();
        H_global.clear();
    }


    return 0;
}

বৃহস্পতিবার, ২২ অক্টোবর, ২০১৫

[Non Standard] uva The easiest way

Problem id : uva The easiest way

It's just an ad-hoc problem.I didn't even use my geometry template :-P .The solution is to take the max possible area for all of these cases.

Code :

#include <bits/stdc++.h>
#define sqr(x) (x*x)
using namespace std;

int main()
{
   int N;
   while(scanf("%d",&N)==1)
   {
       if(N==0)break;

       ///possible answers : w/2 , w , h/4
       ///For all pieces of papers we'll calculate maximum
       ///possible area of the 4 paper birds them and store
       ///them with their index .And finally we'll find the max
       ///of them
       int idx = 0;int ans = 1;
       double max_area=0.00000000f;
       while(N--)
       {
           idx++;
           int t_w,t_h;
           scanf("%d %d",&t_w,&t_h);
           int w,h;
           h = max(t_h,t_w);
           w = t_w+t_h - h;
           double t_area;
           if(h/4*1.00000000f < w)
           t_area = sqr(h/4*1.0000000f);
           else
            t_area = sqr(w);
           if(sqr(w/2*1.000000000f) > t_area)
            t_area = sqr(w/2*1.0000000f);

           if(t_area > max_area)
           {
               ans = idx;
               max_area = t_area;
           }

       }



       printf("%d\n",ans);

   }
    return 0;
}

Random Post 1

Just a piece of advice : You should take graph paper (lots of it :-D ) to contests for graph and geometry problems.[If you're allowed to,of course :-P ]

Photo Courtesy : wikiHow

[Circles] uva elevator

Problem id : uva Elevator

Nota Bene : :P I avoided using EPS in this problem too.(In the circle circle Intersection function [What if r1+r2 = distance but you're checking distance - (r1+r2) > EPS ,will give you a WA verdict ])

:-D

Code :

#include<bits/stdc++.h>

using namespace std;

#define INF 1e9
#define EPS 1e-9
#define PI acos(-1.0) // important constant; alternative #define PI (2.0 * acos(0.0))

double DEG_to_RAD(double d)
{
    return d * PI / 180.0;
}

double RAD_to_DEG(double r)
{
    return r * 180.0 / PI;
}

// struct point_i { int x, y; };    // basic raw form, minimalist mode
struct point_i
{
    int x, y;     // whenever possible, work with point_i
    point_i()
    {
        x = y = 0;    // default constructor *** Usage : point_i p();
    }
    point_i(int _x, int _y) : x(_x), y(_y) {}
};         // user-defined *** Usage : point_i p(5,6);

struct point
{
    double x, y;   // only used if more precision is needed
    point()
    {
        x = y = 0.0;    // default constructor
    }
    point(double _x, double _y) : x(_x), y(_y) {}        // user-defined
    bool operator < (point other) const   // override less than operator
    {
        if (fabs(x - other.x) > EPS)                 // useful for sorting
            return x < other.x;          // first criteria , by x-coordinate // < min to max
        return y < other.y;
    }          // second criteria, by y-coordinate // < min to max

    // use EPS (1e-9) when testing equality of two floating points
    bool operator == (point other) const
    {
        return (fabs(x - other.x) < EPS && (fabs(y - other.y) < EPS));
    }
}; // 2 points have same x and y co-ordinate

double dist(point p1, point p2)                  // Euclidean distance
{
    // hypot(dx, dy) returns sqrt(dx * dx + dy * dy)
    return hypot(p1.x - p2.x, p1.y - p2.y);
}           // return double

// rotate p by theta degrees CCW w.r.t origin (0, 0)
//Going CCW theta is equivalent to going ( CW 360 - theta ) degree
point rotate(point p, double theta)   //The input parameter theta will be provided in degrees //function returns a point
{
    double rad = DEG_to_RAD(theta);    // multiply theta with PI / 180.0
    return point(p.x * cos(rad) - p.y * sin(rad),
                 p.x * sin(rad) + p.y * cos(rad));
}

struct line
{
    double a, b, c;
};          // a way to represent a line
//as generally lines are constructed from 2 points . No such constructor as line(a,b,c)

// the answer is stored in the third parameter (pass by reference) //
//pass by reference syntax : func(int &x){...}  {int x; func(x);}
void pointsToLine(point p1, point p2, line &l)   //Usage : line Ln ; pointsToLine(p1,p2,Ln);
{
    if (fabs(p1.x - p2.x) < EPS)                // vertical line is fine //same x co-ordinate
    {
        l.a = 1.0;
        l.b = 0.0;
        l.c = -p1.x;           // default values
    }
    else
    {
        l.a = -(double)(p1.y - p2.y) / (p1.x - p2.x);
        l.b = 1.0;              // IMPORTANT: we fix the value of b to 1.0
        l.c = -(double)(l.a * p1.x) - p1.y;
    }
}

// not needed since we will use the more robust form: ax + by + c = 0 (see above)
struct line2
{
    double m, c;
};      // another way to represent a line

int pointsToLine2(point p1, point p2, line2 &l)
{
    if (abs(p1.x - p2.x) < EPS)            // special case: vertical line
    {
        l.m = INF;                    // l contains m = INF and c = x_value
        l.c = p1.x;                  // to denote vertical line x = x_value
        return 0;   // we need this return variable to differentiate result //for vertical line the function returns 0
    }
    else
    {
        l.m = (double)(p1.y - p2.y) / (p1.x - p2.x);
        l.c = p1.y - l.m * p1.x;
        return 1;     // l contains m and c of the line equation y = mx + c //returns 1 so non-vertical
    }
}
//Next few functions are just for line[a,b,c] representation
bool areParallel(line l1, line l2)         // check coefficients a & b
{
    return (fabs(l1.a-l2.a) < EPS) && (fabs(l1.b-l2.b) < EPS);
}

bool areSame(line l1, line l2)             // also check coefficient c
{
    return areParallel(l1 ,l2) && (fabs(l1.c - l2.c) < EPS);
}

// returns true (+ intersection point) if two lines are intersect
bool areIntersect(line l1, line l2, point &p)   //pass by reference //saving intersection point to point p
{
    if (areParallel(l1, l2)) return false;            // no intersection
    // solve system of 2 linear algebraic equations with 2 unknowns
    p.x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
    // special case: test for vertical line to avoid division by zero
    if (fabs(l1.b) > EPS) p.y = -(l1.a * p.x + l1.c);
    else                  p.y = -(l2.a * p.x + l2.c);
    return true;
}

struct vec
{
    double x, y;  // name: `vec' is different from STL vector
    vec(double _x, double _y) : x(_x), y(_y) {}
};

vec toVec(point a, point b)         // convert 2 points to vector a->b  AB
{
    return vec(b.x - a.x, b.y - a.y);
} //same as thinking about a point w.r.t. origin

vec scale(vec v, double s)          // nonnegative s = [<1 .. 1 .. >1]
{
    return vec(v.x * s, v.y * s);
}               // shorter__same__longer

point translate(point p, vec v)          // translate p according to v
{
    return point(p.x + v.x , p.y + v.y);
} // the point will move according to vector (vectors x,y component
//would be added to point's x,y co-ordinate)

// convert point and gradient/slope to line
void pointSlopeToLine(point p, double m, line &l)   //If the slope and a single point is known the line can be constructed
{
    l.a = -m;                                               // always -m
    l.b = 1;                                                 // always 1
    l.c = -((l.a * p.x) + (l.b * p.y));
}                // compute this
//Closest point in l from p
void closestPoint(line l, point p, point &ans)
{
    line perpendicular;         // perpendicular to l and pass through p
    if (fabs(l.b) < EPS)                // special case 1: vertical line
    {
        ans.x = -(l.c);
        ans.y = p.y;
        return;
    }

    if (fabs(l.a) < EPS)              // special case 2: horizontal line
    {
        ans.x = p.x;
        ans.y = -(l.c);
        return;
    }

    pointSlopeToLine(p, 1 / l.a, perpendicular);          // normal line
    // intersect line l with this perpendicular line
    // the intersection point is the closest point
    areIntersect(l, perpendicular, ans); //areIntersect returns bool and stores intersection point in answer
}

// returns the reflection of point on a line   .  |  . <-- reflection
void reflectionPoint(line l, point p, point &ans)
{
    point b;
    closestPoint(l, p, b);                     // similar to distToLine
    vec v = toVec(p, b);                             // create a vector
    ans = translate(translate(p, v), v);
}         // translate p twice

double dot(vec a, vec b)
{
    return (a.x * b.x + a.y * b.y);
}

double norm_sq(vec v) //returns the value^2 of the vector
{
    return v.x * v.x + v.y * v.y;
}

// returns the distance from p to the line defined by
// two points a and b (a and b must be different)
// the closest point is stored in the 4th parameter (byref)
double distToLine(point p, point a, point b, point &c)
{
    // formula: c = a + u * ab
    vec ap = toVec(a, p), ab = toVec(a, b);
    double u = dot(ap, ab) / norm_sq(ab);
    c = translate(a, scale(ab, u));                  // translate a to c
    return dist(p, c);
}           // Euclidean distance between p and c

// returns the distance from p to the line segment ab defined by
// two points a and b (still OK if a == b)
// the closest point is stored in the 4th parameter (byref)
double distToLineSegment(point p, point a, point b, point &c)
{
    vec ap = toVec(a, p), ab = toVec(a, b);
    double u = dot(ap, ab) / norm_sq(ab);
    if (u < 0.0)
    {
        c = point(a.x, a.y);                   // closer to a
        return dist(p, a);
    }         // Euclidean distance between p and a
    if (u > 1.0)
    {
        c = point(b.x, b.y);                   // closer to b
        return dist(p, b);
    }         // Euclidean distance between p and b
    return distToLine(p, a, b, c);
}          // run distToLine as above

double angle(point a, point o, point b)    // returns angle aob in rad
{
    vec oa = toVec(o, a), ob = toVec(o, b);
    return acos(dot(oa, ob) / sqrt(norm_sq(oa) * norm_sq(ob)));
}

double cross(vec a, vec b)
{
    return a.x * b.y - a.y * b.x;
}

//// another variant
//int area2(point p, point q, point r) { // returns 'twice' the area of this triangle A-B-c
//  return p.x * q.y - p.y * q.x +
//         q.x * r.y - q.y * r.x +
//         r.x * p.y - r.y * p.x;
//}

// note: to accept collinear points, we have to change the `> 0'
// returns true if point r is on the left side of line pq
bool ccw(point p, point q, point r)
{
    return cross(toVec(p, q), toVec(p, r)) > 0;
}

// returns true if point r is on the same line as the line pq
bool collinear(point p, point q, point r)
{
    return fabs(cross(toVec(p, q), toVec(p, r))) < EPS;
}

int insideCircle(point_i p, point_i c, int r) { // all integer version
  int dx = p.x - c.x, dy = p.y - c.y;
  int Euc = dx * dx + dy * dy, rSq = r * r;             // all integer
  return Euc < rSq ? 0 : Euc == rSq ? 1 : 2; } //inside/border/outside

bool circle2PtsRad(point p1, point p2, double r, point &c) {
  double d2 = (p1.x - p2.x) * (p1.x - p2.x) +
              (p1.y - p2.y) * (p1.y - p2.y);
  double det = r * r / d2 - 0.25;
  if (det < 0.0) return false;
  double h = sqrt(det);
  c.x = (p1.x + p2.x) * 0.5 + (p1.y - p2.y) * h;
  c.y = (p1.y + p2.y) * 0.5 + (p2.x - p1.x) * h;
  return true; }         // to get the other center, reverse p1 and p2
//new Function
bool circ_circ_Intersect(point c1,point c2,double r1,double r2)
{

    double distance = dist(c1,c2);
    if(distance >= r1+r2) //avoided EPS , with EPS got WA
        return false;

    return true;

}
int main()
{
   int L,C,R1,R2;
   while(scanf("%d %d %d %d",&L,&C,&R1,&R2)==4)
   {
if(!L && !C && !R1 && !R2)break;
int ans = 0; //Initially assume can't place the bigger circle
//First check if can place the bigger circle in the triangle or not
if(max(2*R1,2*R2)<=min(L,C))
{
    //Can place the bigger circle
    //So,obviously can place the smaller one
    //Question is do they intersect?
    double R_big = max(R1,R2);
    double R_small = R1+R2 - R_big;
    double H = max(L,C);
    double W = L+C - H;
    point C_big(R_big,W-R_big);
    point C_small(H-R_small,R_small);
     if(!circ_circ_Intersect(C_big,C_small,R_big,R_small))
     {
         ans = 1;
     }
}
if(ans)
    printf("S\n");
else
    printf("N\n");





   }



    return 0;
}

বুধবার, ২১ অক্টোবর, ২০১৫

[Circles] uva Area

Problem id : uva area

The idea is obvious , we'll check if the point is inside all of the four circles and store the number of those points in a variable M.But the problem asks infinite precision which is abstruse .However,in the final answer it asks only 5 decimal places.The way I got AC is just by avoiding EPS.Just do condition checks as you would do with integers.

Code :

#include<bits/stdc++.h>

using namespace std;

#define INF 1e9
#define EPS 1e-9
#define PI acos(-1.0) // important constant; alternative #define PI (2.0 * acos(0.0))

double DEG_to_RAD(double d)
{
    return d * PI / 180.0;
}

double RAD_to_DEG(double r)
{
    return r * 180.0 / PI;
}

// struct point_i { int x, y; };    // basic raw form, minimalist mode
struct point_i
{
    int x, y;     // whenever possible, work with point_i
    point_i()
    {
        x = y = 0;    // default constructor *** Usage : point_i p();
    }
    point_i(int _x, int _y) : x(_x), y(_y) {}
};         // user-defined *** Usage : point_i p(5,6);

struct point
{
    double x, y;   // only used if more precision is needed
    point()
    {
        x = y = 0.0;    // default constructor
    }
    point(double _x, double _y) : x(_x), y(_y) {}        // user-defined
    bool operator < (point other) const   // override less than operator
    {
        if (fabs(x - other.x) > EPS)                 // useful for sorting
            return x < other.x;          // first criteria , by x-coordinate // < min to max
        return y < other.y;
    }          // second criteria, by y-coordinate // < min to max

    // use EPS (1e-9) when testing equality of two floating points
    bool operator == (point other) const
    {
        return (fabs(x - other.x) < EPS && (fabs(y - other.y) < EPS));
    }
}; // 2 points have same x and y co-ordinate

double dist(point p1, point p2)                  // Euclidean distance
{
    // hypot(dx, dy) returns sqrt(dx * dx + dy * dy)
    return hypot(p1.x - p2.x, p1.y - p2.y);
}           // return double

// rotate p by theta degrees CCW w.r.t origin (0, 0)
//Going CCW theta is equivalent to going ( CW 360 - theta ) degree
point rotate(point p, double theta)   //The input parameter theta will be provided in degrees //function returns a point
{
    double rad = DEG_to_RAD(theta);    // multiply theta with PI / 180.0
    return point(p.x * cos(rad) - p.y * sin(rad),
                 p.x * sin(rad) + p.y * cos(rad));
}

struct line
{
    double a, b, c;
};          // a way to represent a line
//as generally lines are constructed from 2 points . No such constructor as line(a,b,c)

// the answer is stored in the third parameter (pass by reference) //
//pass by reference syntax : func(int &x){...}  {int x; func(x);}
void pointsToLine(point p1, point p2, line &l)   //Usage : line Ln ; pointsToLine(p1,p2,Ln);
{
    if (fabs(p1.x - p2.x) < EPS)                // vertical line is fine //same x co-ordinate
    {
        l.a = 1.0;
        l.b = 0.0;
        l.c = -p1.x;           // default values
    }
    else
    {
        l.a = -(double)(p1.y - p2.y) / (p1.x - p2.x);
        l.b = 1.0;              // IMPORTANT: we fix the value of b to 1.0
        l.c = -(double)(l.a * p1.x) - p1.y;
    }
}

// not needed since we will use the more robust form: ax + by + c = 0 (see above)
struct line2
{
    double m, c;
};      // another way to represent a line

int pointsToLine2(point p1, point p2, line2 &l)
{
    if (abs(p1.x - p2.x) < EPS)            // special case: vertical line
    {
        l.m = INF;                    // l contains m = INF and c = x_value
        l.c = p1.x;                  // to denote vertical line x = x_value
        return 0;   // we need this return variable to differentiate result //for vertical line the function returns 0
    }
    else
    {
        l.m = (double)(p1.y - p2.y) / (p1.x - p2.x);
        l.c = p1.y - l.m * p1.x;
        return 1;     // l contains m and c of the line equation y = mx + c //returns 1 so non-vertical
    }
}
//Next few functions are just for line[a,b,c] representation
bool areParallel(line l1, line l2)         // check coefficients a & b
{
    return (fabs(l1.a-l2.a) < EPS) && (fabs(l1.b-l2.b) < EPS);
}

bool areSame(line l1, line l2)             // also check coefficient c
{
    return areParallel(l1 ,l2) && (fabs(l1.c - l2.c) < EPS);
}

// returns true (+ intersection point) if two lines are intersect
bool areIntersect(line l1, line l2, point &p)   //pass by reference //saving intersection point to point p
{
    if (areParallel(l1, l2)) return false;            // no intersection
    // solve system of 2 linear algebraic equations with 2 unknowns
    p.x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
    // special case: test for vertical line to avoid division by zero
    if (fabs(l1.b) > EPS) p.y = -(l1.a * p.x + l1.c);
    else                  p.y = -(l2.a * p.x + l2.c);
    return true;
}

struct vec
{
    double x, y;  // name: `vec' is different from STL vector
    vec(double _x, double _y) : x(_x), y(_y) {}
};

vec toVec(point a, point b)         // convert 2 points to vector a->b  AB
{
    return vec(b.x - a.x, b.y - a.y);
} //same as thinking about a point w.r.t. origin

vec scale(vec v, double s)          // nonnegative s = [<1 .. 1 .. >1]
{
    return vec(v.x * s, v.y * s);
}               // shorter__same__longer

point translate(point p, vec v)          // translate p according to v
{
    return point(p.x + v.x , p.y + v.y);
} // the point will move according to vector (vectors x,y component
//would be added to point's x,y co-ordinate)

// convert point and gradient/slope to line
void pointSlopeToLine(point p, double m, line &l)   //If the slope and a single point is known the line can be constructed
{
    l.a = -m;                                               // always -m
    l.b = 1;                                                 // always 1
    l.c = -((l.a * p.x) + (l.b * p.y));
}                // compute this
//Closest point in l from p
void closestPoint(line l, point p, point &ans)
{
    line perpendicular;         // perpendicular to l and pass through p
    if (fabs(l.b) < EPS)                // special case 1: vertical line
    {
        ans.x = -(l.c);
        ans.y = p.y;
        return;
    }

    if (fabs(l.a) < EPS)              // special case 2: horizontal line
    {
        ans.x = p.x;
        ans.y = -(l.c);
        return;
    }

    pointSlopeToLine(p, 1 / l.a, perpendicular);          // normal line
    // intersect line l with this perpendicular line
    // the intersection point is the closest point
    areIntersect(l, perpendicular, ans); //areIntersect returns bool and stores intersection point in answer
}

// returns the reflection of point on a line   .  |  . <-- reflection
void reflectionPoint(line l, point p, point &ans)
{
    point b;
    closestPoint(l, p, b);                     // similar to distToLine
    vec v = toVec(p, b);                             // create a vector
    ans = translate(translate(p, v), v);
}         // translate p twice

double dot(vec a, vec b)
{
    return (a.x * b.x + a.y * b.y);
}

double norm_sq(vec v) //returns the value^2 of the vector
{
    return v.x * v.x + v.y * v.y;
}

// returns the distance from p to the line defined by
// two points a and b (a and b must be different)
// the closest point is stored in the 4th parameter (byref)
double distToLine(point p, point a, point b, point &c)
{
    // formula: c = a + u * ab
    vec ap = toVec(a, p), ab = toVec(a, b);
    double u = dot(ap, ab) / norm_sq(ab);
    c = translate(a, scale(ab, u));                  // translate a to c
    return dist(p, c);
}           // Euclidean distance between p and c

// returns the distance from p to the line segment ab defined by
// two points a and b (still OK if a == b)
// the closest point is stored in the 4th parameter (byref)
double distToLineSegment(point p, point a, point b, point &c)
{
    vec ap = toVec(a, p), ab = toVec(a, b);
    double u = dot(ap, ab) / norm_sq(ab);
    if (u < 0.0)
    {
        c = point(a.x, a.y);                   // closer to a
        return dist(p, a);
    }         // Euclidean distance between p and a
    if (u > 1.0)
    {
        c = point(b.x, b.y);                   // closer to b
        return dist(p, b);
    }         // Euclidean distance between p and b
    return distToLine(p, a, b, c);
}          // run distToLine as above

double angle(point a, point o, point b)    // returns angle aob in rad
{
    vec oa = toVec(o, a), ob = toVec(o, b);
    return acos(dot(oa, ob) / sqrt(norm_sq(oa) * norm_sq(ob)));
}

double cross(vec a, vec b)
{
    return a.x * b.y - a.y * b.x;
}

//// another variant
//int area2(point p, point q, point r) { // returns 'twice' the area of this triangle A-B-c
//  return p.x * q.y - p.y * q.x +
//         q.x * r.y - q.y * r.x +
//         r.x * p.y - r.y * p.x;
//}

// note: to accept collinear points, we have to change the `> 0'
// returns true if point r is on the left side of line pq
bool ccw(point p, point q, point r)
{
    return cross(toVec(p, q), toVec(p, r)) > 0;
}

// returns true if point r is on the same line as the line pq
bool collinear(point p, point q, point r)
{
    return fabs(cross(toVec(p, q), toVec(p, r))) < EPS;
}

///Circle

int insideCircle(point p, point c, double r) { // all integer version///Modified double version
  double dx = p.x - c.x, dy = p.y - c.y;
  double Euc = dx * dx + dy * dy, rSq = r * r;             // all integer /// Modified double
  if( (Euc-rSq)<= 0.0000000f) ///possibly - or 0 so inside or on the border
  {
//Forget about EPS

  return 1;
  }
  return 0;

  } //inside/border/outside

bool circle2PtsRad(point p1, point p2, double r, point &c) {
  double d2 = (p1.x - p2.x) * (p1.x - p2.x) +
              (p1.y - p2.y) * (p1.y - p2.y);
  double det = r * r / d2 - 0.25;
  if (det < 0.0) return false;
  double h = sqrt(det);
  c.x = (p1.x + p2.x) * 0.5 + (p1.y - p2.y) * h;
  c.y = (p1.y + p2.y) * 0.5 + (p2.x - p1.x) * h;
  return true; }
vector<point>vp;
int main()
{

    int N,a;
    while(scanf("%d %d",&N,&a)==2)
    {
        if(N==0 && a==0)break;
        int N_p;
        N_p = N;
        while(N_p--)
        {
            double x,y;
            cin>>x>>y;
            point temp(x,y);
            vp.push_back(temp);

        }

        point A(0.00000000f,0.0000000f);
        point B(a*1.0000000f,0.0000000f);
        point C(a*1.00000000f,a*1.0000000f);
        point D(0.00000000f,a*1.0000000f);
        int M=0;
        for(int lp=0;lp<N;lp++)
        {
            point temp = vp[lp];

            if(insideCircle(temp,A,a) &&
               insideCircle(temp,B,a) &&
               insideCircle(temp,C,a) &&
               insideCircle(temp,D,a)

                )
            {
                M++;
            }


        }
        double Area =(double) M*a*a/N*1.0000000f;
        printf("%.5lf\n",Area);
vp.clear(); // killer

    }
    return 0;
}