393 - The Doors

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

Moderator: Board moderators

Post Reply
davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

393 - Wrong Answer, I can't belive it. plzzzzzzzzzz help

Post by davor »

The problem is simple but I can't find out why WRONG ANSWER
[pascal]var i,j,k,l,o,n,m:integer;
x1,x2,y1,y2,y3,a1,b1,dis:real;
a:array[0..19,1..5] of real;
b:array[0..19,1..4] of real;

function dist(x1,y1,x2,y2:real):real;
begin
dist:=sqrt(sqr(x1-x2)+sqr(y2-y1));
end;

begin
read(n);
while n>=0 do begin
for i:=1 to n do begin
read(a[i,1],a[i,2],a[i,3],a[i,4],a[i,5]);
b[i,1]:=100000; b[i,2]:=100000; b[i,3]:=100000; b[i,4]:=100000;
end;
a[0,1]:=0; a[0,2]:=5; a[0,3]:=5; a[0,4]:=10; a[0,5]:=10;
b[0,1]:=0; b[0,2]:=0; b[0,3]:=100000; b[0,4]:=100000;
a[n+1,1]:=10; a[n+1,2]:=5; a[n+1,3]:=5; a[n+1,4]:=10; a[n+1,5]:=10;
b[n+1,1]:=100000; b[n+1,2]:=100000; b[n+1,3]:=100000; b[n+1,4]:=100000;
for i:=1 to n+1 do begin
for o:=1 to 4 do begin
for j:=0 to i-1 do begin
for k:=1 to 4 do begin
m:=0;
x1:=a[j,1]; y1:=a[j,k+1];
x2:=a[i,1]; y2:=a[i,o+1];
a1:=(y2-y1)/(x2-y1);
b1:=y1-a1*x1;
for l:=j+1 to i-1 do begin
y3:=a[l,1]*a1+b1;
if (y3<a[l,2]) or ((y3>a[l,3]) and (y3<a[l,4])) or (y3>a[l,5]) then m:=1;
end;
dis:=dist(a[j,1],a[j,k+1],a[i,1],a[i,o+1])+b[j,k];
if (m=0) and (dis<b[i,o]) then b[i,o]:=dis;
end;
end;
if (i=n+1) and (o=1) then writeln(b[i,o]:0:2);
end;
end;
read(n);
end;
end.
[/pascal]

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

393 - The Doors

Post by yolongyi »

My code is getting WA....why??
plz help me...
tell me what is wrong...
or can anyone give me some test case??

Code: Select all

#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;

int vertices, walls;
float W[82][82], X[20], Y[20][4];
float minimum, sum;

bool able(int w1,int v1,int w2,int v2){
	int w;
	float dx,dy, y;
	if(w1-w2==1) return true;
	else{
		dx=X[w1]-X[w2];
		dy=Y[w1][v1]-Y[w2][v2];
		if(w1==0&&v1!=0) return false;
		else if(w2==walls+1&&v2!=0) return false;
		for(w=w1+1;w<w2;w++){
			y = (dy/dx)*X[w] + (Y[w1][v1]-(dy/dx)*X[w1]);
			if(!((Y[w][0]<=y&&y<=Y[w][1]) || (Y[w][2]<=y&&y<=Y[w][3]))) return false;
		}
	}
	return true;
}

int pos(int w,int v){
	if(w==0) return 0;
	else if(w==walls+1) return vertices-1;
	else return (w-1)*4+v+1;
}

void go(int v){
	int i;
	if(sum<minimum){
		if(v==vertices-1) minimum=sum;
		else{
			for(i=v+1;i<vertices;i++){
				if(v==0) sum=0.00;
				if(W[v][i]!=99999.0){
					sum+=W[v][i];
					go(i);
				}
			}
		}
	}
}

void main(){
	int i, j, k, t;
	while(true){
		cin>>walls;
		if(walls==-1) break;
		vertices = walls*4+2;
		X[0]=0.0;X[walls+1]=10.0;
		Y[0][0]=Y[walls+1][0]=5.0;
		for(i=1;i<=walls;i++){
			cin>>X[i];
			for(j=0;j<4;j++) cin>>Y[i][j];
		}
		for(i=0;i<vertices;i++)	for(j=0;j<vertices;j++) W[i][j]=99999.0;
		for(i=0;i<=walls;i++){
			for(j=0;j<4;j++){
				for(k=i+1;k<=walls+1;k++){
					for(t=0;t<4;t++){
						if(able(i,j,k,t)) W[pos(i,j)][pos(k,t)]=sqrt(pow(X[i]-X[k],2)+pow(Y[i][j]-Y[k][t],2));
					}
				}
			}
		}
		sum=0.00;
		minimum=999999.0;
		go(0);
		printf("%.2f\n",minimum);
	}
}
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

yolongyi
New poster
Posts: 5
Joined: Mon Jan 16, 2006 9:19 pm
Location: Korea

I've changed my code but i'm getting WA...

Post by yolongyi »

My previous code does not test all case
so i've changed my code..
but i'm getting WA...
why..
here is my code that changed...

is that bidirectional way??
i dont take care...that

Code: Select all

#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;

int vertices, walls;
float W[100][100], X[30], Y[30][4];
float minimum, sum;

bool able(int w1,int v1,int w2,int v2){
	int w;
	float dx,dy, y;
	if(w1-w2==1) return true;
	else{
		dx=X[w1]-X[w2];
		dy=Y[w1][v1]-Y[w2][v2];
		if(w1==0&&v1!=0) return false;
		else if(w2==walls+1&&v2!=0) return false;
		for(w=w1+1;w<w2;w++){
			y = (dy/dx)*X[w] + (Y[w1][v1]-(dy/dx)*X[w1]);
			if(!((Y[w][0]<=y&&y<=Y[w][1]) || (Y[w][2]<=y&&y<=Y[w][3]))) return false;
		}
	}
	return true;
}

int pos(int w,int v){
	if(w==0) return 0;
	else if(w==walls+1) return vertices-1;
	else return (w-1)*4+v+1;
}

void go(int v){
	int i, j;
	if(sum + sqrt(pow(X[(v+3)/4]-10,2)+pow(Y[(v+3)/4][(v-1)%4]-5,2)) < minimum){
		if(v==vertices-1) minimum=sum;
		else{
			if(v==0) j=1;
			else j=v+4-(v-1)%4;
			for(i=v+1;i<vertices;i++){
				if(W[v][i]!=99999.0){
					sum+=W[v][i];
					go(i);
					sum-=W[v][i];
				}
			}
		}
	}
}

void main(){
	int i, j, k, t;
	while(true){
		cin>>walls;
		if(walls==-1) break;
		vertices = walls*4+2;
		X[0]=0.0;X[walls+1]=10.0;
		Y[0][0]=Y[walls+1][0]=5.0;
		for(i=1;i<=walls;i++){
			cin>>X[i];
			for(j=0;j<4;j++) cin>>Y[i][j];
		}
		for(i=0;i<vertices;i++)	for(j=0;j<vertices;j++) W[i][j]=99999.0;
		for(i=0;i<=walls;i++){
			for(j=0;j<4;j++){
				for(k=i+1;k<=walls+1;k++){
					for(t=0;t<4;t++){
						if(able(i,j,k,t)) W[pos(i,j)][pos(k,t)]=sqrt(pow(X[i]-X[k],2)+pow(Y[i][j]-Y[k][t],2));
					}
				}
			}
		}
		sum=0.00;
		minimum=999999.0;
		go(0);
		printf("%.2f\n",minimum);
	}
}
[/b]
hi... I am a student stydying Computer Programming. Plz give me your hand.. I'll give U too if I can..

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

Why would you use backtracking when something like dijkstra would work?

Tritri
New poster
Posts: 5
Joined: Mon Mar 06, 2006 2:04 am

Post by Tritri »

Hi, I'm think your code forces the path to past just over the vertex and if you see the example you will see that the solution can 'pass' across the door without 'touch' it.

Tritri
New poster
Posts: 5
Joined: Mon Mar 06, 2006 2:04 am

Post by Tritri »

I try to solve this problem but the response was allways WA too... and this problem is very difficult to test and debug. Can someone who has solved this prob. try to pass this test and say the correct result??

Code: Select all

18
1 3 3.5 8.5 9
1.5 1 3 4 5
1.7 0.5 0.6 0.7 1
2 8.4 8.5 9.5 9.6
2.1 1 2 3 4
3 3 3.5 8.5 9
3.5 1 3 4 5
3.7 0.5 0.6 0.7 1
4 8.4 8.5 9.5 9.6
6.1 1 2 3 4
6.2 5 5.5 6.1 6.2
6.4 1 1.5 2 2.4
7 4 5 6 7
7.5 1 1.2 1.3 1.4
7.6 2 2.1 2.2 2.3
7.7 6 6.1 7 7.5
8 2 3 4 5
8.5 1 2 9.5 10
-1

Post Reply

Return to “Volume 3 (300-399)”