HackerRank Geometry – A Circle and a Square – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: A Circle and a Square

Scor cont: 35.0 / 35

Submission status: Accepted

Submission score: 1.0

Submission ID: 464727903

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/a-circle-and-a-square/problem

Cerinta

In this challenge, you must implement part of a [raster graphics](https://en.wikipedia.org/wiki/Raster_graphics) editor that takes the coordinates of a circle and a square as input and draws them as filled-in shapes on a rectangular canvas.

---

The rectangular canvas consists of uniformly sized square pixels, and is $w$ pixels wide, and $h$ pixels high. Each point on the canvas belongs to a pixel, the intersection of two pixels has zero area, and each pixel is completely contained within the canvas. 

The [Cartesian coordinate system](https://en.wikipedia.org/wiki/Cartesian_coordinate_system) set up in the following way: 

- Point $(0, 0)$ is the center of the top-left pixel of the canvas.
- Point $(w - 1, 0)$ is the center of the top-right pixel of the canvas.
- Point $(0, h - 1)$ is the center of the bottom-left pixel of the canvas. 
- Point $(w - 1, h - 1)$ is the center of the bottom-right pixel of the canvas. 

Thus, all pixel centers have integer coordinates and if the center of a pixel has coordinates $(x_c, y_c)$, then point $(x, y)$ belongs to the pixel if and only if $x \in [x_c-0.5,x_c+0.5]$ and $y \in [y_c-0.5,y_c+0.5]$. The two shapes should be drawn like so:

- The *circle* is centered at the integer coordinates $(x_{circle}, y_{circle})$ and has non-negative integer radius $r$. A pixel should be *black* as a part of the circle if and only if the Euclidean distance from the pixel's center to the center of the circle is *not* greater than $r$.

![image](https://s3.amazonaws.com/hr-assets/0/1487518469-2517e4de82-image-circle.png)

- The *square* is defined by the integer coordinates of two of its opposite corners $(x_1, y_1)$ and $(x_3, y_3)$. A pixel should be *black* as a part of the square if and only if its center falls within the square or along its border. The coordinates of different corners of the square do not coincide.

![image](https://s3.amazonaws.com/hr-assets/0/1487517200-3693c19c3f-image-square.png)

Given $h$, $w$, and the definition of the circle and the square, print a raster image of the canvas where each character is either a `.` (denoting a *white* pixel outside of both shapes) or a `#` (denoting a *black* pixel that's part of a shape).

**Note:** The first pixel of the first line of output should correspond to the top-left corner of the canvas.

Input Format

The first line contains two space-separated integers describing the respective values of $w$ (canvas width) and $h$ (canvas height).		
The second line contains three space-separated integers describing the respective values of $x_{circle}$, $y_{circle}$, and $r$ defining a circle with radius $r$ centered at $(x_{circle}, y_{circle})$. 		
The third line contains four space-separated integers describing the respective values of $x_1, y_1, x_3, y_3$ defining a square with opposite corners at $(x_1, y_1)$ and $(x_3, y_3)$.

Output Format

Print $h$ lines where each line contains $w$ characters. Each character must be either a `.` (to denote a white pixel) or a `#` (to denote a black pixel). The first pixel of the first line of output corresponds to the top-left corner of the canvas.

Constraints

- $10 \le w, h \le 100$  
- $-100 \le x_{circle}, y_{circle}, x_1, y_1, x_3, y_3 \le 200$  
- $0 \le r \le 100$

Cod sursa

#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;
}

HackerRank Geometry – A Circle and a Square