#include #include #include #include using namespace std; const char GRID = 'G'; const char CIRCLE = 'C'; const double PI = 4*atan(1.0); class intersection { public: double x, y; char type; }; vector areas; vector line1, line2; double calcSlice(intersection& i1, intersection& i2, double r) // calculate slice of circle with given secant and radius r { double dx = i1.x - i2.x; double dy = i1.y - i2.y; double secant = sqrt(dx*dx + dy*dy); double ans = r*r*asin(secant/(2*r)) - secant*sqrt(r*r-secant*secant/4)/2; return ans; } bool checkInside(double x, double y, double r) { return (x*x+y*y <= r*r); } void calcInOutIntersection(double xa, double ya, double xb, double yb, double r, intersection a[], int & nInt) { if (ya == yb) { double x = sqrt(r*r - ya*ya); if (x > xa && x > xb) // check if this solution out of range x = -x; a[nInt].x = x; a[nInt].y = ya; a[nInt].type = CIRCLE; nInt++; } else { double y = sqrt(r*r - xa*xa); if (y > ya && y > yb) y = -y; a[nInt].x = xa; a[nInt].y = y; a[nInt].type = CIRCLE; nInt++; } } void calcOutOutIntersection(double xa, double ya, double xb, double yb, double r, intersection a[], int & nInt) { if (xa == xb) { // vertical line if (xa <= -r || xa >= r) return; // miss circle double yhigh = sqrt(r*r - xa*xa); double ylow = -yhigh; if (ya < yb) { if (ya < ylow && ylow < yb) { a[nInt].x = xa; a[nInt].y = ylow; a[nInt++].type = CIRCLE; } if (ya < yhigh && yhigh < yb) { a[nInt].x = xa; a[nInt].y = yhigh; a[nInt++].type = CIRCLE; } } else { if (yb < yhigh && yhigh < ya) { a[nInt].x = xa; a[nInt].y = yhigh; a[nInt++].type = CIRCLE; } if (yb < ylow && ylow < ya) { a[nInt].x = xa; a[nInt].y = ylow; a[nInt++].type = CIRCLE; } } } else { // horizontal line if (ya <= -r || ya >= r) return; // miss circle double xhigh = sqrt(r*r - ya*ya); double xlow = -xhigh; if (xa < xb) { if (xa < xlow && xlow < xb) { a[nInt].x = xlow; a[nInt].y = ya; a[nInt++].type = CIRCLE; } if (xa < xhigh && xhigh < xb) { a[nInt].x = xhigh; a[nInt].y = ya; a[nInt++].type = CIRCLE; } } else { if (xb < xhigh && xhigh < xa) { a[nInt].x = xhigh; a[nInt].y = ya; a[nInt++].type = CIRCLE; } if (xb < xlow && xlow < xa) { a[nInt].x = xlow; a[nInt].y = ya; a[nInt++].type = CIRCLE; } } } } double calcArea1(intersection a[], int nInt, double r, double x1, double y1, double x2, double y2) /* * calcs area for regions with 4, 3, 2 or 1 grid point */ { double area = 0.0; a[nInt] = a[0]; for(int i=0; i= r) return area; else if (y1 <= -r && y2 >= r) return area; // check if center of circle is in intersection of rect and circle for(int i=0; i 0) return calcArea1(ints, nInt, r, x1, y1, x2, y2); else if (nInt == 0) { if (x1*x2 < 0 && y1*y2 < 0) return r*r*PI; else return 0.0; } else if (nInt == 2) { double area = calcSlice(ints[0], ints[1], r); //cout << x1 << ',' << y1 << ' ' << x2 << ',' << y2 << ' ' << area << endl; if (x1*x2 < 0 && y1*y2 < 0) return r*r*PI - area; // center of circle in square else return area; } else if (nInt == 4) return calcArea2(ints, nInt, r, x1, y1, x2, y2); else // if (nInr == 6 || nInt == 8) return calcArea1(ints, nInt, r, x1, y1, x2, y2); } int main() { int r, delx, dely, startx, starty; double percent; cin >> r >> delx >> dely >> startx >> starty >> percent; int xlow = startx - ((startx + r)/delx)*delx; if (xlow > -r) xlow -= delx; int ylow = starty - ((starty + r)/dely)*dely; if (ylow > -r) ylow -= dely; int xhigh = startx + ((r-startx)/delx)*delx; if (xhigh < r) xhigh += delx; int yhigh = starty + ((r-starty)/dely)*dely; if (yhigh < r) yhigh += dely; // cout << xlow << '-' << xhigh << ' ' << ylow << '-' << yhigh << endl; for(int x = xlow; x < xhigh; x += delx) { for(int y = ylow; y < yhigh; y += dely) { double area = calcArea(x, y, x+delx, y+dely, r); if (area > 0.0) areas.push_back(area); } } sort(areas.begin(), areas.end()); double cutoff = percent*areas[areas.size()-1]; double sum = 0; double smallCount = 0; for( double area : areas) { // cout << area << endl; if (area < cutoff) smallCount++; sum += area; } if (fabs(sum - r*r*PI)/(r*r*PI) > 0.0001) cout << "ERROR: sum of all pieces < pizza area"; cout << smallCount << endl; }