## 10011 - Where Can You Hide?

Moderator: Board moderators

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
Edit: Just my e-mail... Thank you!
Last edited by tgoulart on Sat Feb 24, 2007 8:35 am, edited 1 time in total.
Thiago Sonego Goulart - UFMG/Brazil

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Email sent.

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

### 10011 WA

Could anybody send me AC code? (altertain.AT.gmail.com)

I have received WA 33 times. I had tested all examples in this board, but I couldn't find counterexample.

Here is my code

#define err 0.00000001

struct pnt {
long double x,y;
};

long double dis(pnt a,pnt b)
{
return sqrtl( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}

long double segdis(pnt sa,pnt sb,pnt pa) //선분과 점 사이 거리
{
long double a,b,c,t;

a=dis(sa,pa);
b=dis(sb,pa);
c=dis(sa,sb);
if (a<b)
t=a,a=b,b=t;
if (a*a>b*b+c*c || c<err)
return b;
t=(a+b+c)/2.0;
t=sqrtl(t*(t-a)*(t-b)*(t-c));
return 2.0*t/c;
}

long double gdis(long double a,long double b,long double x,long double y)
{
return fabsl((a*x+b*y)/sqrtl(a*a+b*b));
}

pnt c,p,q,w1,w2,o;
long double r;

int main()
{
int t;

scanf("%d",&t);
while (t--) {
cin>>c.x>>c.y>>r>>p.x>>p.y;
if ((c.x-p.x)*(c.x-p.x)+(c.y-p.y)*(c.y-p.y)<=r*r) {
printf("0.000\n");
continue;
}
if (segdis(o,p,c)>r-err) {
printf("%.3lf\n",0.0);
continue;
}
long double dp=dis(c,p)-r;
if (c.y==r) {
long double a,b;
a=0,b=1;
dp=min(dp,gdis(a,b,p.x,p.y));
a=1,b=(r*r-c.x*c.x)/(2.0*c.x*c.y);
dp=min(dp,gdis(a,b,p.x,p.y));
}
else {
long double a,b;
a=1,b=(-c.x*c.y+r*sqrtl(c.x*c.x+c.y*c.y-r*r))/(c.y*c.y-r*r);
dp=min(dp,gdis(a,b,p.x,p.y));
a=1,b=(-c.x*c.y-r*sqrtl(c.x*c.x+c.y*c.y-r*r))/(c.y*c.y-r*r);
dp=min(dp,gdis(a,b,p.x,p.y));
}
if (dp<0)
dp=0;
printf("%.3llf\n",dp);
}
return 0;
}
Lee, Taeyoon

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

I had tested all examples in this board, but I couldn't find counterexample.

2
2 2 2 5 2
10 10 10 19 19

I would appreciate it.
Lee, Taeyoon

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
you can use an old one to post..

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

### who

2
2 2 2 5 2
10 10 10 19 19

I would appreciate it.
Lee, Taeyoon

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hello,

I get:
1.000
2.728

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
tgoulart wrote:Hi,

I've got several WA for this problem. I pass all the I/O I found in this forum and maybe it's just a precision error... Can someone give me the correct output for this random input?

http://www.ecomp.furg.br/~tgoulart/input.txt
Hello, I got WA all the time.
I thought my algorithm is right. Maybe the precsion is fault.
Could somone offer the right output for the input above?
Thx tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
I can't upload it to this server for now, but if you tell me your e-mail I can send you.
Thiago Sonego Goulart - UFMG/Brazil

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Hi everybody!
I got WA for many times here, but I still cannot understand why. I have tried many ways of i/o, also I listened to someone here who said they ask min(distance2tree,min-distance2lines), but result is the same - WA failure at ~1.271 secs. I suspect it may be because of the precision, that I don't know much about. Please,ppl, watch my code:

Code: Select all

``````#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char *argv[]) {
int casen,ci;
float e1,e2,e3,e4,e5,e6,a,b,c,x,y,u,v,r,d,l,l1,ny1,ny2,nx1,nx2,t,m,e0;

cin >> casen;

for (ci=0;ci<casen;ci++){
cin >> x >> y >> r >> u >> v;

l = sqrt(x*x+y*y);
m = sqrt(l*l-r*r);

t = m*m - r*r + x*x + y*y;

a = 4*y*y + 4*x*x;
b = 4*t*y;
c = t*t-4*x*x*m*m;

d = b*b - 4*a*c;

ny1 = (b + sqrt(d))/(2*a);
ny2 = (b - sqrt(d))/(2*a);

nx1 = (t - 2*ny1*y)/(2*x);
nx2 = (t - 2*ny2*y)/(2*x);

a = ny1;
b = -nx1;
t = sqrt(a*a+b*b);

e1 = (a*u + b*v)/t;
if (e1<0) e1 = -e1;

a = ny2;
b = -nx2;
t = sqrt(a*a+b*b);

e2 = (a*u + b*v)/t;
if (e2<0) e2 = -e2;

e3 = u*ny1 - v*nx1;
e4 = x*ny1 - y*nx1;
e5 = u*ny2 - v*nx2;
e6 = x*ny2 - y*nx2;

e0 = sqrt((u-x)*(u-x)+(v-y)*(v-y)) - r;

if ((e3*e4<=0)||(e5*e6<=0)) {
cout << "0.000" << endl;
}else{
if ((e0<e1)&&(e0<e2)) {
cout << e0 << endl;
}else if ((e2<e1)&&(e2<e0)) {
cout << e2 << endl;
}else{
cout << e1 << endl;

}
}

return EXIT_SUCCESS;
}

``````
Now I lay me down to sleep...
my profile

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil
Why don't you take a look at the first page of this topic? There is a huge input file and the solution to it.

Also, the distance must be printed with 3 digits after the decimal point.
Thiago Sonego Goulart - UFMG/Brazil

ZhangChi
New poster
Posts: 4
Joined: Tue Oct 18, 2005 6:55 pm
Contact:
Amazing!!! I have passed all the test case in 10011.in, but I still get WA!!!

help!! I believe my algorithm have no problem, precision error??

Code: Select all

``````
#include <stdio.h>
#include <math.h>

const double Pi = 3.1415926535897932384626;
const double EPS = 1E-8;

struct Tpoint
{
double x, y;
};

const Tpoint o = { 0, 0 };

Tpoint Tc, house;
Tpoint bound;
double R, minL;

double sqr (double x)
{
return x * x;
}

double dist (Tpoint a, Tpoint b)
{
return sqrt (sqr (a.x - b.x) + sqr (a.y - b.y));
}

double det (Tpoint p1, Tpoint p2)
{
double lenA = dist (p1, o), lenB = dist (p2, o);
double temp = acos ((p1.x * p2.x + p1.y * p2.y) / lenA / lenB);

if (temp < -EPS) temp = temp + Pi * 2;
return temp;
}

void rotate (Tpoint p, double sinA, double cosA, Tpoint &newp)
{
newp.x = p.x * cosA - p.y * sinA;
newp.y = p.x * sinA + p.y * cosA;
}

void getline (Tpoint a, Tpoint b, double &A, double &B, double &C)
{
A = a.y - b.y;
B = b.x - a.x;
C = - (a.x * A + a.y * B);
}

void updata (double A, double B, double C)
{
double len = fabs (A * house.x + B * house.y + C) / sqrt (sqr (A) + sqr (B));

if (len < minL) minL = len;
}

void calc ()
{
double len	= dist (o, Tc);
double _len = sqrt (sqr (o.x - Tc.x) + sqr (o.y - Tc.y) - sqr (R));
double A, B, C;

rotate (Tc, R / len, _len / len, bound);
rotate (Tc, -R / len, _len / len, bound);

minL = 0;
if (fabs (det (bound, house) + det (house, bound) - det (bound, bound)) > EPS) return;
if (dist (o, house) < _len) return;

minL = dist (Tc, house) - R;

getline (o, bound, A, B, C); updata (A, B, C);
getline (o, bound, A, B, C); updata (A, B, C);
}

int main()
{
freopen ("input.txt", "r", stdin);
freopen ("output.txt", "w", stdout);

int casenum;

scanf ("%d", &casenum);
while (casenum > 0)
{
scanf ("%lf%lf%lf", &Tc.x, &Tc.y, &R);
scanf ("%lf%lf", &house.x, &house.y);

calc ();
printf ("%.3lf\n", minL);
casenum--;
}

return 0;
}

``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases.

Input:

Code: Select all

``````28
5 5 2 10 10
5 5 2 -10 -10
5 5 2 1 1
0 5 5 0 -1
0 5 5 0 11
0 5 5 10 1
0 5 5 10 -1
0 5 5 10 -1
2 2 2 5 2
10 10 10 19 19
5 5 2 2 2
5 5 2 8 8
5 5 6 12 12
-5 5 6 -12 12
-5 -5 6 -12 -12
5 -5 6 12 -12
5 5 1 12 12
20 0 3 7 -7
-9.6 4.3 2.1 -19.2 7.9
5 5 5 11 5
5 5 5 0.1 6.42
5 5 5 0.1 5.998
5 5 5 0.0005 10
20 -24 6 25 -30
-10 2 5 -18 -2
0 5 5 10 0
5 5 2 0 0
0 5 5 0 0``````
Output:

Code: Select all

``````4.000
0.000
0.000
0.000
1.000
1.000
0.000
0.000
1.000
2.728
0.000
2.243
3.899
3.899
3.899
3.899
2.400
0.000
3.517
1.000
0.100
0.001
0.001
1.810
3.676
0.000
0.000
0.000``````
Hope these help.