313 - Intervals

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

Moderator: Board moderators

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

313 - Intervals

Post by Chung Ha, Yun » Fri Aug 09, 2002 9:01 pm

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);
ComputeInterval(Light, Pipe, radius, data);
}
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:

Post by arnsfelt » Fri Aug 09, 2002 9:44 pm

I have some good test data on my homepage, - try it out.

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

I find my mistake...but WA

Post by Chung Ha, Yun » Sat Aug 10, 2002 4:13 pm

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?

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Tue Oct 07, 2003 1:40 pm

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:

Post by Dominik Michniewski » Fri Mar 12, 2004 12:06 pm

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

Post by junbin » Mon Mar 15, 2004 2:42 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:

Post by Dominik Michniewski » Mon Mar 15, 2004 9:29 am

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!

Post by Moha » Sat Sep 11, 2004 5:14 pm

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

Post by StatujaLeha » Sun Jun 26, 2005 8:54 pm

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:

Post by sidky » Sat Jul 02, 2005 4:35 pm

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:

Post by yiuyuho » Tue Feb 27, 2007 10:05 am

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?

Post Reply

Return to “Volume 3 (300-399)”