We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Geometry
  4. A Circle and a Square
  5. Discussions

A Circle and a Square

Sort by

recency

|

6 Discussions

|

  • ruben_3o
     + 0 comments

    Here is a solution with integer numbers. using distance between points and cross product.

    #include <bits/stdc++.h>

using namespace std;

int sgn( int x ) {
    if( x==0 ) return 0;
    return ( x < 0 ? -1 : 1 );
}

struct point {
    int x, y;

    point() : x(0), y(0) {}
    point( int a, int b) : x(a), y(b) {}

    bool operator == (const point &p ) const { return (x==p.x && y==p.y);}
    void operator *= (const int k ) { this->x *= k; this->y *= k; }

    point operator - (const point &p ) const { return point(x-p.x, y-p.y); }
    point operator + (const point &p ) const { return point(x+p.x, y+p.y); }

    point rotate ( ) { return point( -y, x ); }
    int distance( const point &p ) const { return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y); }
    int cross( const point &p ) const { return x*p.y - p.x*y; }
};

int n, m, radius;
point centerCircle;
vector<point> rectangule( 5 );

bool isInCircle( const point &p ) {
    return (p.distance( centerCircle ) <= radius*radius);
}

void buildRectangule( int x1, int y1, int x2, int y2){
    point centerRectangule((x1+x2)/2, (y1+y2)/2);

    rectangule[ 0 ] = point(x1,y1);
    rectangule[ 1 ] = centerRectangule + (rectangule[ 0 ] - centerRectangule).rotate();
    rectangule[ 2 ] = point(x2,y2);
    rectangule[ 3 ] = centerRectangule + (rectangule[ 2 ] - centerRectangule).rotate();
    rectangule[ 4 ] = rectangule[ 0 ];
}

bool isInRectangule( const point &p ) {
    int sgns[ 4 ];
    for( int i = 0; i < 4; ++i ) {
        point vector1 = rectangule[ i+1 ] - rectangule[ i ];
        point vector2 = p - rectangule[ i ];
        sgns[ i ] = sgn( vector1.cross(vector2) );
    }
		
		// the sign of parallel edges have to be the same or 0
    return ( sgns[ 0 ]*sgns[ 2 ] >= 0 && sgns[ 1 ]*sgns[ 3 ] >= 0);
}

int main() {
    int x1,y1,x2,y2;
    cin >> m >> n;

    cin >> centerCircle.y >> centerCircle.x >> radius;
    centerCircle *= 10; radius *= 10;
    
    cin >> y1 >> x1 >> y2 >> x2;
    buildRectangule(x1*10, y1*10, x2*10, y2*10);

    point current;
    for( int x=0; x < n; ++x ) {
        for( int y=0; y < m; ++y ) {
            current = point( x, y );
            current *= 10;

            if( isInCircle( current ) || isInRectangule( current ) )
                cout << "#";
            else
                cout << ".";
        }
        cout << endl;
    }
    return 0;
}

  • LazyMist
     + 0 comments

    Alternatively, for the square part, one can rotate the coordinate system so as to have the square aligned with the horizontal and vertical directions. Then it is enough to check each coordinate separately i.e. given a point (x, y) whether x is between x1 and x3 (all values after rotation), and similarly for y. In this case we operate with floating point numbers, and need to be careful with precision errors (use small epsilon when comparing numbers).

  • bhishmapitamah
     + 1 comment

    Checking if the points lies inside a square can be done without any floating point operations. Two hints (References almost contain the solution to this problem. Do not open them if you still want to figure your own way out just by using the hints) :

    • You can calculate the other veticies of the squre using the two diagonal points given using some maniputaion of vectors. The only factor of division by 2 can be taken to the other side of the inequalities while comparison, to avoid division. Reference
    • The actual condition for checking if point is inside the squre can be either done by the method of comparing the sum of areas or even better the dot product of edges of squre and the vector from vertex to point.Reference

  • Strongbow
     + 0 comments

    Calculating the boundaries of the square is the nub of this question. I had considered a square to be enclosed by two pairs of parallel lines at right angles and sides of equal length which it is. The output from my code for the square somtimes differed a little from HR output. Changing from int to float types helped, but the answer seems to need the hacker to consider the square as 2 triangles.

  • mikelee89
     + 0 comments

    New learning.. Thank you for the question. Converted the editorial version to Java

    public class Solution
{

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        String[] wh = scanner.nextLine().split(" ");

        int w = Integer.parseInt(wh[0]);

        int h = Integer.parseInt(wh[1]);

        String[] circleXCircleY = scanner.nextLine().split(" ");

        int circleX = Integer.parseInt(circleXCircleY[1]);

        int circleY = Integer.parseInt(circleXCircleY[0]);

        int r = Integer.parseInt(circleXCircleY[2]);

        Circle circle = new Circle(new Point(circleX, circleY), r);

        String[] x1Y1X3Y3 = scanner.nextLine().split(" ");

        int x1 = Integer.parseInt(x1Y1X3Y3[1]);

        int y1 = Integer.parseInt(x1Y1X3Y3[0]);

        int x3 = Integer.parseInt(x1Y1X3Y3[3]);

        int y3 = Integer.parseInt(x1Y1X3Y3[2]);

        Square square = Square.read(x1, y1, x3, y3);

        // Write Your Code Here
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (circle.contains(i, j) || square.contains(i, j)) {
                    System.out.print("#");
                } else {
                    System.out.print(".");
                }
            }
            System.out.println();
        }
        scanner.close();
    }

    static class Point {
        double x;
        double y;

        Point(double i, double j) {
            this.x = i;
            this.y = j;
        }
    }

    static class Circle {
        Point center;
        int r;

        public Circle(Point pt, int r) {
            this.center = pt;
            this.r = r;
        }

        boolean contains(int i, int j) {
            double di = i - center.x;
            double dj = j - center.y;
            return (di * di) + (dj * dj) <= r * r;
        }

    }

    static class Square {
        Point p1, p2, p3, p4;

        public Square(Point p1, Point p2, Point p3, Point p4) {
            this.p1 = p1;
            this.p2 = p2;
            this.p3 = p3;
            this.p4 = p4;
        }


        boolean contains(int i, int j) {
            return new Triangle(p1, p3, p2).contains(new Point(i, j)) || new Triangle(p1, p3, p4).contains(new Point(i, j));
        }

        static Square read(int x1, int y1, int x3, int y3) {

            //center points
            double cx = (x1 + x3) / 2.0;
            double cy = (y1 + y3) / 2.0;

            //vector from center to x1, y1
            double dx = x1 - cx;
            double dy = y1 - cy;

            //vecors perpendicular
            double px = -1 * dy;
            double py = dx;

            double x2 = cx + px;
            double y2 = cy + py;

            double x4 = cx - px;
            double y4 = cy - py;

            return new Square(new Point(x1, y1), new Point(x2, y2), new Point(x3, y3), new Point(x4, y4));
        }
    }

    static class Triangle {
        Point p1, p2, p3;
        double area;

        public Triangle(Point p1, Point p2, Point p3) {
            this.p1 = p1;
            this.p2 = p2;
            this.p3 = p3;
            this.area = Math.abs(((p3.x - p1.x) * (p2.y - p1.y)) - ((p3.y - p1.y) * (p2.x - p1.x))) / 2;
        }


        boolean contains(Point p) {
            return this.area == new Triangle(p1, p2, p).area + new Triangle(p2, p3, p).area + new Triangle(p3, p1, p).area;
        }
    }

}