## 313 - Intervals

Moderator: Board moderators

Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

### 313 - Intervals

Easy Algorithm... But I recieve WA, again.

Sample test set is perfect.

Would you help me...?

[cpp]
#include<stdio.h>
#include<math.h>

typedef struct _coordinate
{
int x;
int y;
} Coordinate;

typedef struct _interval
{
double start;
double end;
} Interval;

void ComputeInterval(Coordinate Light, Coordinate Pipe, int radius, Interval& data);
void BubbleSort(Interval* data, int num);
void Swap(Interval& a, Interval& b);

int main()
{
Coordinate Pipe, Light;
Interval data[500];
int N, i, radius, count = 0;
double max;

while(scanf("%d", &N) > 0 && N != 0)
{
scanf("%d %d", &Light.x, &Light.y);
for(i=0;i<N;i++)
{
scanf("%d %d %d", &Pipe.x, &Pipe.y, &radius);
}
BubbleSort(data, N);
/* for(i=0;i<N;i++)
printf("start : %.2lf , end : %.2lf\n", data.start, data.end);*/
if(count != 0) printf("\n");
for(i=0;i<N;i++)
{
printf("%.2lf ", data.start);
max = data.end;
while(i < N-1 && data.end >= data[i+1].start)
{
max = data[i+1].end > max ? data[i+1].end : max;
i++;
}
printf("%.2lf\n", max);
}
count++;
}
return 0;
}

void BubbleSort(Interval* data, int num)
{
for(int i=0;i<num-1;i++)
for(int j=num-1;j>=i+1;j--)
if(data[j-1].start > data[j].start)
Swap(data[j], data[j-1]);
}

void Swap(Interval& a, Interval& b)
{
Interval temp;
temp.start = a.start;
temp.end = a.end;
a.start = b.start;
a.end = b.end;
b.start = temp.start;
b.end = temp.end;
}

void ComputeInterval(Coordinate Light, Coordinate Pipe, int radius, Interval& data)
{
if(Light.x == Pipe.x)
{
double angle = asin((double)radius / ((double)Light.y - (double)Pipe.y));
double range = Light.y * tan(angle);
data.start = (double)Light.x - range;
data.end = (double)Light.x + range;
}
else
{
double angle1 = asin((double)radius / sqrt(pow((double)Light.x - (double)Pipe.x, 2.0) + pow((double)Light.y - (double)Pipe.y, 2.0)));
double angle2 = atan2((double)Light.x > (double)Pipe.x ? (double)Light.x - (double)Pipe.x : (double)Pipe.x - (double)Light.x, (double)Light.y - (double)Pipe.y);
double range1 = tan(angle2 - angle1) * (double)Light.y;
double range2 = tan(angle2 + angle1) * (double)Light.y;
if(Light.x > Pipe.x)
{
data.start = (double)Light.x - range2;
data.end = (double)Light.x - range1;
}
else
{
data.start = (double)Light.x + range1;
data.end = (double)Light.x + range2;
}
}
}
[/cpp]

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
I have some good test data on my homepage, - try it out.

Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

### I find my mistake...but WA

I have three situations.

1. Light's x-coordinate == Pipe's x-coordinate

2. Light's x-coordinate > Pipe's x-coordinate

3. Light's x-coordinate < Pipe's x-coordinate

any more situation?

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
According to arnsfelt's sample input -617.975 should be rounded down to
-617.98 and not rounded up like my program did for a while. Maybe that helps someone.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
First time I got WA like dumb dan for the same reason... (rounding on the same value).
Now I change calculating proccess, got the same values (but without using any trigonometric function) and got Acc.

Maybe common problem with rounding is placed in this functions ? COuld anyone explain me it ?

Best regards
DM

PS. I change one in my code : without using tan(alfa + beta) I use formula which decompose it into tan(alfa) and tan(beta), which I can compute without using tan() function ...
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
this question is a bit strict on the floating point numbers.. so try trying your epsilon value.. also, try finding another way to evaluate the answer.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I avoid to use any math functions like tan(),acos() (excepted one sqrt() ) and no use of epsilon value and got Acc. So I think that on linux trigonometric functions can generate precision errors.
When I print results I use simple ".2lf" format and it's enough to solve this problem. I also think that on unix machines behaviour of printf could be a bit different than on Windows machines, so -x.xx5 could be rounded in different way in this operating systems (I use Windows, -x.xx5 is rounded to -x.xx and it differs from outputs which I found, but got Acc).

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

### no problem with precision!

In My accepted code I use acos, cos, sin and epsilon is 1e-10 and also using cout.presicion(2) to show the answer. I think it is enough!!.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

### I just got ACC !!!

I got WA many times. My first algoruthm used trigonometric functions as tan,atan,acos,sin. I tried an input date given by arnsfelt and got discrepancy only in one number in the 100-th shares! Then I improved my algorithm: i don't used trigonometric function. And got ACC. My time is 0:00.045. Success to you in the decision of a problem.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
I just solved this problem. I used trigonometric functions tan, atan2 and asin. At first I got WA. But, after that I just changed the printing part to:

Code: Select all

``````printf("%.2lf %.2lf\n",x1 - EPSILON,x2 - EPSILON);
``````
although

Code: Select all

``````printf("%.2lf %.2lf\n",x1 + EPSILON,x2 + EPSILON);
``````
produced WA. Can anyone please explain why?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
dumb dan wrote: -617.975 should be rounded down to
-617.98 and not rounded up
Theoretically that's a mistake, am I correct?

What I am trying to say is, Mathematically -617.975 should be -617.97 in 2dc?