10969 - Sweet Dream

[Cho]

Do I miss anything? I don't understand what makes so few submissions for this problem.
Anyway, I got WA.
Here is some io: 10969.zip
Please let me know if you find my mistake.

[mf]

For your io, my output is exactly the same, and I get WA, too.

[wook]

Can you tell me how I can approach this problem?

I can't find any striking algorithm!

Thanks for advices.
wook

[Cho]

For your io, my output is exactly the same, and I get WA, too.

The problem setter has just sent me a pm. The submitted solution will be rejudged and we just need to wait for the new result.

Can you tell me how I can approach this problem?

In my solution, each circle is represented by their radius, center and an angular range. For any new circle, the initial range is [-Pi, Pi]. All existing circles will be checked to see if it's covered by the new one. If so, it's range will decreased or even broken into two ranges.

[mf]

Can you tell me how I can approach this problem?

My approach is to find the length of visible boundary for each circle separately.

To do this, I find the points of intersections of the circle with disks above it, sort them by the angle from the circle's center, and for each angular interval, check if this interval is visible (by checking, if its midpoint is visible.)

[Moha]

For each circle, ad the begining, I assume it`s interval is [0,2*PI]. and then for each circle 'i' I determine if it has 2 intersection point with another circle "j>i" and then i divide it`s orginal interval to some new interval. Thus for each circle i have a list of it`s intervals.

[wook]

thanks to, Moha, mf and Cho.

what a stupid mistake! ignore it.

[Cho]

For each fan-shapes, if it is visible(i.e. have no intersected areas) i can just add the area of this shape;

Area? We are computing perimeter.

[wook]

Yes;
the output is

"the total perimeter of part of discs"


Why did I knew the object is that!
Stupid mistake, ignore it.

Anyway, Thank you very much for advices.

[wook]

I wrote a program, but I got WA.

my outputs for Cho's test inputs above is exactly the same with yours;
but I can't understand why it gives WA.

is it a precision error?
my epsilon value is 1e-10...

If there are some tricky special cases, please let me know them.
or, if there are extremely fussy or unusual cases, please give me some..

Thank you again.

[Cho]

How about this one:

Code: Select all

1
2
5 1 1
5 1 1

Anwser: 31.416

[wook]

thanks, Cho.

I hadn't notice these cases(two or more circles are the same!).
now I modified my code, and got AC

Thank you very much again.

[arsalan_mousavian]

i've got many WA on this problem and my program passes all the inputs above , can someone give some tricky IO ?
thanks in Advance . . .

[tzupengwang]

Can anyone point out what's wrong with my code?
I think it's a Monte Carlo problem
Is it a precision error or is there a problem with my algorithm?

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define PI (3.14159265)
#define MAXN 743

int num;
double point[105][3];
double cosine[MAXN],sine[MAXN];

bool inside(double a,double b,int k)
{
    if ((a-point[k][0])*(a-point[k][0])+(b-point[k][1])*(b-point[k][1])<=point[k][2]*point[k][2])
        return true;
    return false;
}
double MONTE_CARLO()
{
    double ans=0;
    for (int i=0;i<num;i++)
    {
        double A=point[i][0],B=point[i][1],C=point[i][2];
        int count=MAXN;
        for (int j=0;j<MAXN;j++)
        {
            double ta=A+cosine[j]*C,tb=B+sine[j]*C;
            for (int k=i+1;k<num;k++)
            {
                //if (k==i)continue;
                if (inside(ta,tb,k))
                {
                    count--;
                    break;
                }
            }
        }
        ans+=C*count;
    }
    ans*=2*PI/MAXN;
    return ans;
}

int main()
{
    int amm;
    scanf("%d",&amm);
    while (amm--)
    {
        scanf("%d",&num);
        for (int i=0;i<num;i++)
        {
            scanf("%lf%lf%lf",&point[i][2],&point[i][0],&point[i][1]);
        }
        for (int i=0;i<MAXN;i++)
        {
            cosine[i]=cos(PI*2*i/(MAXN));
            sine[i]=sin(PI*2*i/(MAXN));
        }

        double ans=MONTE_CARLO();
        printf("%.3lf\n",ans);
    }
    return 0;
}

[tzupengwang]

Or is there a faster math algorithm?