10969  Sweet Dream
Moderator: Board moderators
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.
Anyway, I got WA.
Here is some io: 10969.zip
Please let me know if you find my mistake.
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.mf wrote:For your io, my output is exactly the same, and I get WA, too.
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.wook wrote:Can you tell me how I can approach this problem?
My approach is to find the length of visible boundary for each circle separately.Can you tell me how I can approach this problem?
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
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.
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 1e10...
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.
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 1e10...
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..
How about this one:
Anwser: 31.416
Code: Select all
1
2
5 1 1
5 1 1

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

 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?
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 ((apoint[k][0])*(apoint[k][0])+(bpoint[k][1])*(bpoint[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;
}

 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?