313 - Intervals

[Chung Ha, Yun]

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]

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

[Chung Ha, Yun]

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]

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]

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

[junbin]

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]

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

[Moha]

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]

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]

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]

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