Problem Bee

From Progteam

(Difference between revisions)
Jump to: navigation, search
 
Line 1: Line 1:
-
{{bounty|hjfreyer}}
+
{{solved|jjx203}}
{{problem
{{problem
|name=Problem Bee
|name=Problem Bee
Line 11: Line 11:
-
== Partial Solution ==
+
== 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]]
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]]
Line 17: Line 17:
import java.util.*;
import java.util.*;
-
public class d{
+
public class Main{
static double L;
static double L;

Latest revision as of 17:47, 25 March 2008

Checkmark.jpg This problem has been solved by jjx203.


Problem Bee
Problem Number 1518
Sorter: Mlc413
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1518



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


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 Main{
	static double L;
	
	public static void main(String[] args){
		Scanner reader=new Scanner(System.in);
		while(reader.hasNext()){
			L=reader.nextDouble();
			double Ax=reader.nextDouble();
			double Ay=reader.nextDouble();
			double Bx=reader.nextDouble();
			double By=reader.nextDouble();
			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);
			}
						
			String answer=String.valueOf(Math.round(distance*1000)/1000.0);
			while(answer.length()<5){
				answer=answer+"0";
			}
			System.out.println(answer);
		}
	}
	
	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;
	}
}
Personal tools