#include #include #include using namespace std; class point{ public: double x; double y; point(double sx=0, double sy=0){ x = sx; y = sy; } }; class line{ public: point start; point end; line(){ start.x = 0; start.y = 0; end.x = 0; end.y = 0; } line(point sp, point ep){ start = sp; end = ep; } }; bool Intersects(line l, double r, vector& intersections){ intersections.resize(0); if(l.start.y == l.end.y){ // l is horizontal double the_y = l.start.y; double first_x = -1*sqrt(r*r-the_y*the_y); double second_x = -1*first_x; if((first_x >= l.start.x && first_x <= l.end.x) || (first_x >= l.end.x && first_x <= l.start.x)){ point p; p.x = first_x; p.y = the_y; intersections.push_back(p); } if ((second_x >= l.start.x && second_x <= l.end.x) || (second_x >= l.end.x && second_x <= l.start.x)){ point p; p.x = second_x; p.y = the_y; intersections.push_back(p); } } else{ // l is vertical double the_x = l.start.x; double first_y = -1*sqrt(r*r-the_x*the_x); double second_y = -1*first_y; if((first_y >= l.start.y && first_y <= l.end.y) || (first_y >= l.end.y && first_y <= l.start.y)){ point p; p.x = the_x; p.y = first_y; intersections.push_back(p); } if((second_y >= l.start.y && second_y <= l.end.y) || (second_y >= l.end.y && second_y <= l.start.y)){ point p; p.x = the_x; p.y = second_y; intersections.push_back(p); } } return intersections.size()>0; } // how many times does the rectangle defined by the 4 lines hit the circle // with radius r? int Count_Intersections(line bottom, line right, line top, line left, double r){ int num_intersections = 0; vector dummy; if(Intersects(top, r, dummy)) num_intersections++; if(Intersects(bottom, r, dummy)) num_intersections++; if(Intersects(left, r, dummy)) num_intersections++; if(Intersects(right, r, dummy)) num_intersections++; return num_intersections; } bool Inside(point p, double r){ if((p.x*p.x + p.y*p.y) <= r*r) return true; else return false; } double Distance(point p, point q){ return sqrt(pow(p.x-q.x,2) + pow(p.y-q.y,2)); } // area of a segment defined by 2 points on the circle double Circular_Segment(point p, point q, double r){ double theta = 2* asin(Distance(p,q)/(2*r)); if(theta > 180){ cout << "Circular segment angle > 180: Do something" << endl; } return .5*r*r*(theta-sin(theta)); } // for when a square hits a circle at a right angle- one intersection point // on a vertical edge, one on a horizontal edge double Right_Angle_Area(point p, point corner, point q, double r){ // First, find the triangle area made by the points double length = max(abs(p.x-corner.x),abs(q.x-corner.x)); double height = max(abs(p.y-corner.y),abs(q.y-corner.y)); double area = .5 * length * height; // next add in the circle segment area area = area + Circular_Segment(p,q,r); return area; } int Count_Inside_Circle(const vector& corners, double r){ int num_inside = 0; for(int i = 0; i < corners.size(); i++){ if(Inside(corners[i], r)) num_inside++; } return num_inside; } int main(){ int R, dx, dy, x, y; cin >> R >> dx >> dy >> x >> y; double r = R - .0000000001; double p; cin >> p; while(x > -1*r){ x = x-dx; } while(x+dx < -r) x = x+dx; while (y > -1*r){ y = y-dy; } while(y+dy < -r) y = y+dy; // now (x,y) is the lower-left corner of the outermost relavent rectangle double circle_area = M_PI*r*r; double circumference = 2*M_PI*r; int num_ok = 0; vector areas; for(int cur_x = x; cur_x <= r; cur_x = cur_x + dx){ for(int cur_y = y; cur_y <=r; cur_y = cur_y + dy){ // cout << "cur_x = " << cur_x << " cur_y = " << cur_y << endl; vector corners(4); corners[0] = point(cur_x, cur_y); // lower left corners[1] = point(cur_x+dx, cur_y); // lower right corners[2] = point(cur_x+dx, cur_y+dy); // upper right corners[3] = point(cur_x, cur_y+dy); // upper left point lower_left = corners[0]; point lower_right = corners[1]; point upper_right = corners[2]; point upper_left = corners[3]; int num_inside = Count_Inside_Circle(corners, r); double cur_area; vector sides(4); sides[0] = line(corners[0],corners[1]); // bottom sides[1] = line(corners[1], corners[2]); // right sides[2] = line(corners[2], corners[3]); // top sides[3] = line(corners[3], corners[0]); //left line bottom = sides[0]; line right = sides[1]; line top = sides[2]; line left = sides[3]; if(num_inside == 0){ // case 1- no lines intersect the square point p; int num_line_intersections = Count_Intersections(sides[0],sides[1],sides[2],sides[3],r); if(num_line_intersections == 0) cur_area = 0; // case 2- 1 line intersects. This means that the area is the whole // cicle minus the part outside the one intersection, or _just_ that slice else if(num_line_intersections == 1){ vector intersections; for(int i = 0; i < 4; i++){ if(Intersects(sides[i], r, intersections)){ if((cur_x < 0 && cur_x+dx >=0) && (cur_y < 0 && cur_y + dy >= 0)) cur_area = M_PI*r*r-Circular_Segment(intersections[0], intersections[1], r); else cur_area = Circular_Segment(intersections[0], intersections[1],r); } } } else if(num_line_intersections == 2 || num_line_intersections == 3){ vector first_intersections; vector second_intersections; vector third_intersections; for(int i = 0; i < 4; i++){ if(Intersects(sides[i], r, first_intersections)){ for(int j = i+1; j < 4; j++){ if(Intersects(sides[j], r, second_intersections)){ if(num_line_intersections == 3){ for(int k = j+1; k < 4; k++){ if(Intersects(sides[k], r, third_intersections)) k=4; } } i = 4; j = 4; } } } } double seg1 = 0; double seg2 = 0; double seg3 = 0; if(first_intersections.size() > 1) seg1 = Circular_Segment(first_intersections[0], first_intersections[1], r); if(second_intersections.size() > 1) seg2 = Circular_Segment(second_intersections[0], second_intersections[1], r); if(num_line_intersections == 3 && third_intersections.size() > 1) seg3 = Circular_Segment(third_intersections[0], third_intersections[1], r); if((cur_x < 0 && cur_x + dx >= 0) && (cur_y < 0 && cur_y + dy >= 0)){ cur_area = M_PI*r*r - seg1 - seg2; if(num_line_intersections == 3) cur_area = cur_area - seg3; } else{ cur_area = max(seg1, seg2) - min(seg1, seg2); // I don't think it's possible to have a 3-intersection // segment that doesn't include the origin } } /* // case 3 and 4: 2 or 3 line intersects. // Then there are 4 points of intersection // on 2 parallel lines. The area is the Circle_segment of one line - // the circle segment of the other line // In case 4, we have an additional circle segment around the corner to // chop off else if(num_line_intersections == 2 || num_line_intersections == 3){ vector intersections; vector other_intersections; vector case4_intersections; point corner; if(Intersects(sides[0], r, intersections)){ // bottom Intersects(sides[2],r, other_intersections); // so find top if(num_line_intersections == 3){ if(!Intersects(sides[1],r,case4_intersections)){ Intersects(sides[3],r,case4_intersections); } } } else{ // right Intersects(sides[1], r, intersections); Intersects(sides[3],r, other_intersections); //so find bottom if(num_line_intersections == 3){ if(!Intersects(sides[0],r,case4_intersections)) Intersects(sides[2],r,case4_intersections); } } cur_area = Circular_Segment(intersections[0], intersections[1], r) - Circular_Segment(other_intersections[0], other_intersections[1], r); if(cur_area < 0) cur_area = cur_area * -1; if(num_line_intersections == 3){ cur_area = cur_area - Circular_Segment(case4_intersections[0], case4_intersections[1], r); } } */ // case 5: 4 line intersections The area is the whle circle minus // circular segments on all 4 sides/ else{ cur_area = M_PI*r*r; for(int i = 0; i < sides.size(); i++){ vector cur_intersects; Intersects(sides[i], r, cur_intersects); cur_area = cur_area - Circular_Segment(cur_intersects[0], cur_intersects[1], r); } } } else if(num_inside == 1){ // if one point is inside the circle, then find which one, and the // area is the right angle intersection for(int i = 0; i < corners.size(); i++){ if(Inside(corners[i], r)){ vector intersections; point intersection1; point intersection2; Intersects(sides[i],r,intersections); intersection1 = intersections[0]; int prev = i-1; if(prev < 0) prev = 3; Intersects(sides[prev],r, intersections); intersection2 = intersections[0]; cur_area = Right_Angle_Area(intersection1, corners[i], intersection2, r); } } } else if(num_inside == 2){ // If 2 points are inside they have to be adjacent, so they will form // a rectangle inside the circle plus a right-angle segments vector intersections; double length; double height; point corner; double extra_area; if((Inside(lower_left,r) && Inside(lower_right,r)) || (Inside(upper_left,r) && Inside(upper_right,r))){ point left_point; Intersects(left, r, intersections); left_point = intersections[0]; point right_point; Intersects(right, r, intersections); right_point = intersections[0]; length = dx; if(Inside(lower_left,r)){ if(abs(left_point.y) < abs(right_point.y)){ corner.x = right_point.x; corner.y = left_point.y; height = corner.y-lower_left.y; } else{ corner.x = left_point.x; corner.y = right_point.y; height = corner.y - lower_right.y; } } else{ if(abs(left_point.y) < abs(right_point.y)){ corner.x = right_point.x; corner.y = left_point.y; height = upper_right.y-corner.y; } else{ corner.x = left_point.x; corner.y = right_point.y; height = upper_left.y-corner.y; } } extra_area = Right_Angle_Area(right_point, corner, left_point, r); } if((Inside(lower_left,r) && Inside(upper_left,r)) || (Inside(lower_right,r) && Inside(upper_right,r))){ point top_point; point bottom_point; Intersects(top, r, intersections); top_point = intersections[0]; Intersects(bottom, r, intersections); bottom_point = intersections[0]; height = dy; if(Inside(lower_left,r)){ if(abs(top_point.x) < abs(bottom_point.x)){ corner.x = top_point.x; corner.y = bottom_point.y; length = top_point.x - upper_left.x; } else{ corner.x = bottom_point.x; corner.y = top_point.y; length = bottom_point.x-lower_left.x; } } else{ if(abs(top_point.x) < abs(bottom_point.x)){ corner.x = top_point.x; corner.y = bottom_point.y; length = lower_right.x-top_point.x; } else{ corner.x = bottom_point.x; corner.y = top_point.y; length = lower_right.x-bottom_point.x; } } extra_area = Right_Angle_Area(top_point, corner, bottom_point, r); } length = abs(length); height = abs(height); cur_area = length*height+extra_area; } else if(num_inside == 3){ // Then one corner is outside. Find it. cur_area = dx*dy; for(int i = 0; i < 4; i++){ if(!Inside(corners[i], r)){ point p1, p2; vector intersections; Intersects(sides[i], r, intersections); p1 = intersections[0]; int prev = i-1; if(prev == -1) prev = 3; Intersects(sides[prev], r, intersections); p2 = intersections[0]; double length = max(abs(p1.x-corners[i].x), abs(p2.x-corners[i].x)); double height = max(abs(p1.y-corners[i].y), abs(p2.y-corners[i].y)); // subtract out the triangle made by p1, p2, and the corner cur_area = cur_area - .5* length * height; // add back in the circular segment cur_area = cur_area + Circular_Segment(p1,p2,r); } } } else // num_inside = 4 cur_area = dx*dy; //cout << "Area = " << cur_area << endl; if(cur_area > 0) areas.push_back(cur_area); } } double max_area = 0; for(int i = 0; i < areas.size(); i++) if(areas[i] > max_area) max_area = areas[i]; int num_too_small = 0; double min_good_area = max_area * p; for(int i = 0; i < areas.size(); i++){ if(areas[i] < min_good_area) num_too_small++; } cout << num_too_small << endl; return 0; }