## 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

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

### 10969 - Sweet Dream

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:
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
Can you tell me how I can approach this problem?

I can't find any striking algorithm!

wook
Sorry For My Poor English..

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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:
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

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
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..

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
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
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..

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

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

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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

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

Or is there a faster math algorithm?