10011 - Where Can You Hide?

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Sun Dec 24, 2006 2:29 am

Edit: Just my e-mail... :wink:

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
Location: TORONTO, CANADA

Post by daveon » Sun Dec 24, 2006 10:21 pm

Email sent.

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

10011 WA

Post by altertain » Sat Jan 13, 2007 10:49 am

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;
}
Lee, Taeyoon

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

Post by daveon » Sun Jan 14, 2007 7:23 pm

Please use an existing thread for this problem.

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

I had tested..

Post by altertain » Mon Jan 15, 2007 9:43 am

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.
Lee, Taeyoon

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Jan 15, 2007 4:59 pm

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
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

who

Post by altertain » Tue Jan 16, 2007 4:42 am

Could anybody tell me AC answer about this?

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
Location: TORONTO, CANADA

Post by daveon » Sat Jan 20, 2007 9:41 pm

Hello,

I get:
1.000
2.728

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

Post by windows2k » Sat Feb 24, 2007 5:02 am

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

tgoulart
New poster
Posts: 42
Joined: Sat Oct 21, 2006 8:37 am
Location: Alegrete, Brazil

Post by tgoulart » Sat Feb 24, 2007 6:03 am

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:

Post by andysoft » Sat Jun 23, 2007 9:56 pm

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

Post by tgoulart » Sun Jun 24, 2007 1:35 am

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:

Post by ZhangChi » Sat Aug 18, 2007 3:53 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Mar 21, 2008 8:56 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”