Problem Bee

(Difference between revisions)
 Revision as of 17:44, 25 March 2008 (view source)Hjfreyer (Talk | contribs)← Older edit Revision as of 17:45, 25 March 2008 (view source)Hjfreyer (Talk | contribs) Newer edit → Line 1: Line 1: + {{bounty|hjfreyer}} + {{problem + |name=Problem Bee + |number=1518 + |difficulty + |type=Geometry + |sorter=Mlc413 + |source + }} + '''Problem Bee''' is problem number 1518 on the Peking University ACM site. - As promised, I implemented my idea and get the following solution. This problem can actually be solved in constant time(Actually an linear time algorithm will yield Time Exceed Limit Error). This should be a fairly straightforward problem, but it really take me a long time to implement such a simple and stupid idea. -[[User:jjx203|jjx203]] - ---- == Partial Solution == == Partial Solution == + As promised, I implemented my idea and get the following solution. This problem can actually be solved in constant time(Actually an linear time algorithm will yield Time Exceed Limit Error). This should be a fairly straightforward problem, but it really take me a long time to implement such a simple and stupid idea. -[[User:jjx203|jjx203]] +

import java.util.*;                                                                                                                                                                                                                                                                                                                                                                                                                               import java.util.*;
Line 160:                                                                                                                                                                                                                                                                                                                                                                                                                                        Line 170:
}                                                                                                                                                                                                                                                                                                                                                                                                                                                 }

+ + + [[Category:Geometry]] + [[Category:Grid]]

Revision as of 17:45, 25 March 2008

 Sorter: Mlc413 Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1518

Problem Bee is problem number 1518 on the Peking University ACM site.

Partial Solution

As promised, I implemented my idea and get the following solution. This problem can actually be solved in constant time(Actually an linear time algorithm will yield Time Exceed Limit Error). This should be a fairly straightforward problem, but it really take me a long time to implement such a simple and stupid idea. -jjx203

```import java.util.*;

public class d{
static double L;

public static void main(String[] args){
if((L==0.0)&&(Ax==0.0)&&(Bx==0.0)&&(Ay==0.0)&&(By==0.0)){
break;
}

double distance=0.0;
Pair AIndex=getIndex(Ax, Ay);
//	System.out.println("AIndex:m:"+AIndex.x+"    AIndex:n:"+AIndex.y);
Pair BIndex=getIndex(Bx, By);
//	System.out.println("BIndex:m:"+BIndex.x+"    BIndex:n:"+BIndex.y);

if((AIndex.x!=BIndex.x)||(AIndex.y!=BIndex.y)){
distance+=AIndex.d+BIndex.d;
int steps=traverse(AIndex.x, AIndex.y, BIndex.x, BIndex.y);
//		System.out.println("Steps"+steps);
distance+=steps*L*Math.sqrt(3);
}else{
distance=dist(Ax, Ay, Bx, By);
}

}
}
}

public static int traverse(double m, double n, double tar_m, double tar_n){
double dm=Math.abs(m-tar_m);
double dn=Math.abs(n-tar_n);

if(dm>=2*dn-1){
return (int)dm;
}

if(isOdd(dm)){
if(isOdd(m)){
dn=dn-(dm-1)/2;
}else{
dn=dn-(dm+1)/2;
}
}else{
dn=dn-dm/2;
}
return (int)(dm+2*dn);
/*		Pair p1=getCoor(m, n);
Pair p2=getCoor(tar_m, tar_n);
double cur_x=p1.x;
double cur_y=p1.y;
double tar_x=p2.x;
double tar_y=p2.y;
int steps=0;
while((cur_x!=tar_x)||(cur_y!=tar_y)){
if((cur_x>tar_x)&&(cur_y>tar_y)){
cur_x=cur_x-3*L/2;
cur_y=cur_y-Math.sqrt(3)*L/2;
}else if((cur_x>tar_x)&&(cur_y<=tar_y)){
cur_x=cur_x-3*L/2;
cur_y=cur_y+Math.sqrt(3)*L/2;
}else if((cur_x<=tar_x)&&(cur_y>tar_y)){
cur_x=cur_x+3*L/2;
cur_y=cur_y-Math.sqrt(3)*L/2;
}else{
cur_x=cur_x+3*L/2;
cur_y=cur_y+Math.sqrt(3)*L/2;
}
steps++;
//		System.out.println("cur_x:"+cur_x+"     cur_y:"+cur_y);
}
return steps;*/
}

public static Pair getIndex(double x, double y){
double m=Math.floor(x/(1.5*L));//x will be between m and m+1
double sq3=Math.sqrt(3);
double dy=sq3*L*Math.pow(-1,m+1)/4+sq3*L/4;
double n=Math.floor((y-dy)/(sq3*L));//y will be between n and n+1

Pair p=getCoor(m,n);
double d1=dist(p.x, p.y, x, y);
if(d1<L){
Pair q=new Pair(m, n, d1);
return q;
}

p=getCoor(m+1,n);
d1=dist(p.x, p.y, x, y);
if(d1<L){
Pair q=new Pair(m+1, n, d1);
return q;
}

p=getCoor(m,n+1);
d1=dist(p.x, p.y, x, y);
if(d1<L){
Pair q=new Pair(m, n+1, d1);
return q;
}

p=getCoor(m+1,n+1);
d1=dist(p.x, p.y, x, y);
if(d1<L){
Pair q=new Pair(m+1, n+1, d1);
return q;
}
return null;
}

public static Pair getCoor(double m, double n){
double x=3*L*m/2;
double sq3=Math.sqrt(3);
double y=sq3*L*n+sq3*L*Math.pow(-1,m+1)/4+sq3*L/4;
Pair p=new Pair(x, y);
return p;
}

public static double dist(double x, double y, double x2, double y2){
return Math.sqrt(Math.pow(x-x2,2)+Math.pow(y-y2,2));
}

public static boolean isOdd(double n){
return ((int)n)%2!=0;
}
}

class Pair{
public double x;
public double y;
public double d;

public Pair(double x, double y){
this.x=x;
this.y=y;
}

public Pair(double x, double y, double d){
this.x=x;
this.y=y;
this.d=d;
}
}
```