Soluție HackerRank pentru A Circle and a Square, subdomeniul Geometry, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: A Circle and a Square
- Domeniu: Geometry
- Limbaj: C++14
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
Cerință
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.
- 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.
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 ≤ w, h ≤ 100
- -100 ≤ x_circle, y_circle, x_1, y_1, x_3, y_3 ≤ 200
- 0 ≤ r ≤ 100
Cod sursă
#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;
}