10969 - Sweet Dream

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

10969 - Sweet Dream

Post by Cho » Tue Nov 15, 2005 7:01 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Nov 18, 2005 7:38 pm

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

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Sun Nov 20, 2005 1:18 pm

Can you tell me how I can approach this problem?

I can't find any striking algorithm!

Thanks for advices.
wook
Sorry For My Poor English.. :)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Nov 20, 2005 7:46 pm

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Nov 20, 2005 9:04 pm

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

My Algorithm

Post by Moha » Tue Nov 22, 2005 4:30 pm

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
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Wed Nov 23, 2005 1:29 pm

thanks to, Moha, mf and Cho.

what a stupid mistake! ignore it. :)
Last edited by wook on Thu Nov 24, 2005 9:47 am, edited 1 time in total.
Sorry For My Poor English.. :)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Nov 23, 2005 5:01 pm

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.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Thu Nov 24, 2005 9:48 am

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.
Sorry For My Poor English.. :)

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Fri Nov 25, 2005 9:36 am

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.
Sorry For My Poor English.. :)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Nov 25, 2005 11:01 am

How about this one:

Code: Select all

1
2
5 1 1
5 1 1
Anwser: 31.416

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Sat Nov 26, 2005 5:03 am

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.
Sorry For My Poor English.. :)

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Mon Jun 12, 2006 11:41 pm

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 . . .
In being unlucky I have the record.

tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

10969 - Sweet Dream

Post by tzupengwang » Wed Mar 20, 2013 11:00 am

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
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

Re: 10969 - Sweet Dream

Post by tzupengwang » Wed Mar 20, 2013 2:09 pm

Or is there a faster math algorithm? :-?

Post Reply

Return to “Volume 109 (10900-10999)”