Page 4 of 4

Posted: Sun Dec 24, 2006 2:29 am
by tgoulart
Edit: Just my e-mail... :wink:

Thank you!

Posted: Sun Dec 24, 2006 10:21 pm
by daveon
Email sent.

10011 WA

Posted: Sat Jan 13, 2007 10:49 am
by altertain
Could anybody send me AC code? (altertain.AT.gmail.com)

I have received WA 33 times. :cry:

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

Posted: Sun Jan 14, 2007 7:23 pm
by daveon
Please use an existing thread for this problem.

I had tested..

Posted: Mon Jan 15, 2007 9:43 am
by 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.

Posted: Mon Jan 15, 2007 4:59 pm
by 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..

who

Posted: Tue Jan 16, 2007 4:42 am
by altertain
Could anybody tell me AC answer about this?

2
2 2 2 5 2
10 10 10 19 19

I would appreciate it.

Posted: Sat Jan 20, 2007 9:41 pm
by daveon
Hello,

I get:
1.000
2.728

Posted: Sat Feb 24, 2007 5:02 am
by windows2k
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 :D

Posted: Sat Feb 24, 2007 6:03 am
by tgoulart
I can't upload it to this server for now, but if you tell me your e-mail I can send you.

Posted: Sat Jun 23, 2007 9:56 pm
by 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;
}


Posted: Sun Jun 24, 2007 1:35 am
by 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.

Posted: Sat Aug 18, 2007 3:53 pm
by 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;
}



Posted: Fri Mar 21, 2008 8:56 pm
by 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.