10011 - Where Can You Hide?

[tgoulart]

Edit: Just my e-mail...

Thank you!

[daveon]

Email sent.

[altertain]

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.

Please help me.

In addition, I don't know right answer about "2 2 2 5 2" and "10 10 10 19 19". If you know right answer, please reply.

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;
}

[daveon]

Please use an existing thread for this problem.

[altertain]

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

Could you tell me AC answer about this?

2
2 2 2 5 2
10 10 10 19 19

I would appreciate it.

[helloneo]

what daveon meant was don't open a new thread if there is a thread already
you can use an old one to post..

[altertain]

Could anybody tell me AC answer about this?

2
2 2 2 5 2
10 10 10 19 19

I would appreciate it.

[daveon]

Hello,

I get:
1.000
2.728

[windows2k]

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]

I can't upload it to this server for now, but if you tell me your e-mail I can send you.

[andysoft]

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;
}

[tgoulart]

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.

[ZhangChi]

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[2];
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[0]);
	rotate (Tc, -R / len, _len / len, bound[1]);

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

	minL = dist (Tc, house) - R;

	getline (o, bound[0], A, B, C); updata (A, B, C);
	getline (o, bound[1], 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]

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.