Area(a tired problem)..

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

Your email is never published nor shared. Required fields are marked *