Page 1 of 2

10969 - Sweet Dream

Posted: Tue Nov 15, 2005 7:01 pm
by 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.

Posted: Fri Nov 18, 2005 7:38 pm
by mf
For your io, my output is exactly the same, and I get WA, too.

Posted: Sun Nov 20, 2005 1:18 pm
by wook
Can you tell me how I can approach this problem?

I can't find any striking algorithm!

Thanks for advices.
wook

Posted: Sun Nov 20, 2005 7:46 pm
by Cho
mf wrote: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.
wook wrote: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.

Posted: Sun Nov 20, 2005 9:04 pm
by 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.)

My Algorithm

Posted: Tue Nov 22, 2005 4:30 pm
by 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.

Posted: Wed Nov 23, 2005 1:29 pm
by wook
thanks to, Moha, mf and Cho.

what a stupid mistake! ignore it. :)

Posted: Wed Nov 23, 2005 5:01 pm
by Cho
wook wrote: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.

Posted: Thu Nov 24, 2005 9:48 am
by 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.

Posted: Fri Nov 25, 2005 9:36 am
by 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.

Posted: Fri Nov 25, 2005 11:01 am
by Cho
How about this one:

Code: Select all

1
2
5 1 1
5 1 1
Anwser: 31.416

Posted: Sat Nov 26, 2005 5:03 am
by wook
thanks, Cho.

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

Thank you very much again.

Posted: Mon Jun 12, 2006 11:41 pm
by 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 . . .

10969 - Sweet Dream

Posted: Wed Mar 20, 2013 11:00 am
by 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;
}


Re: 10969 - Sweet Dream

Posted: Wed Mar 20, 2013 2:09 pm
by tzupengwang
Or is there a faster math algorithm? :-?