Noli turbare circulos meos!: [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;
}
Noli turbare circulos meos!

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

[Circles] uva Area

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন
