The Problem is about count the whole area of some overlapped circles..
All the circle’s radius is one;
Input the coordinate of the centre of the circle..
And print the area at the screen. (accurate to 0.01)
Sample Input
3
1 1
1 2
2 2
Sample Output
6.84
#include<stdio.h> #include<math.h> int n; const double pi=3.1415926535897932384626433832795; double sum; FILE *fo,*fp; typedef struct ss { int x; int y; }cir; cir cirs[110]; void qs(int l,int r) { int i=l,j=r; cir x=cirs[l]; while (i<j) { while (i<j&&(cirs[j].x>x.x||(cirs[j].x==x.x&&cirs[j].y>=x.y)))j--; cirs[i]=cirs[j]; while (i<j&&(cirs[i].x<x.x||(cirs[i].x==x.x&&cirs[i].y<=x.y)))i++; cirs[j]=cirs[i]; } cirs[i]=x; if (l<i-1)qs(l,i-1); if (i+1<r)qs(i+1,r); } void work() { scanf("%d",&n); int i; for (i=0;i<n;i++) { scanf("%d%d",&cirs[i].x,&cirs[i].y); } qs(0,n-1); int j; bool ls=false,rs=false,s=false,l=false; double s1=pi-(pi/3+sqrt(3)/2),s2=pi-(1+pi/2),s3=pi*5/12-sqrt(3)/2; for (i=0;i<n;i++) { ls=rs=s=l=false; for (j=0;j<n;j++) { if (i-j) { if (cirs[j].x==cirs[i].x-1&&cirs[j].y==cirs[i].y-1)ls=true; else if (cirs[j].x==cirs[i].x-1&&cirs[j].y==cirs[i].y+1)rs=true; else if (cirs[j].x==cirs[i].x-1&&cirs[j].y==cirs[i].y)s=true; else if (cirs[j].x==cirs[i].x&&cirs[j].y==cirs[i].y-1)l=true; } } if (!ls&&!rs&&!s&&!l)sum+=pi; else if ((s&&!ls&&!rs&&!l)||(l&&!s&&!ls&&!rs))sum+=pi-s1; else if ((ls&&!rs&&!l&&!s)||(rs&&!l&&!s&&!ls))sum+=pi-s2; else if (ls&&rs&&!l&&!s)sum+=pi-s2-s2; else if ((ls&&s&&!rs&&!l)||(rs&&s&&!ls&&!l)||(l&&ls&&!s&&!rs))sum+=pi-s1-(s2-s3); else if (l&&rs&&!ls&&!s)sum+=pi-s1-s2; else if (l&&s&&!rs&&!ls)sum+=pi-s1-(s1-s3); else if (ls&&s&&rs&&!l)sum+=pi-s1-2*(s2-s3); else if (l&&ls&&rs&&!s)sum+=pi-s1-s2-(s2-s3); else if (l&&s&&rs&&!ls)sum+=pi-s1-(s1-s3)-(s2-s3); else if (l&&s&&ls&&!rs)sum+=pi-s1-(s1-s3); else if (l&&s&&ls&&rs)sum+=pi-s1-(s1-s3)-(s2-s3); } printf("%.2lfn",sum); } int main() { freopen("area.in","r",stdin); freopen("area.out","w",stdout); work(); return 0; } |
Post a Comment