313 - Intervals
Moderator: Board moderators
-
- 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);
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]
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]
-
- 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?
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?
-
- 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 ...
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- 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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
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!!.
-
- 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.

-
- 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:
although
produced WA. Can anyone please explain why?
Code: Select all
printf("%.2lf %.2lf\n",x1 - EPSILON,x2 - EPSILON);
Code: Select all
printf("%.2lf %.2lf\n",x1 + EPSILON,x2 + EPSILON);