Freckles

From Progteam

Revision as of 04:08, 22 February 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Mlc413.


Freckles
Problem Number 2560
Sorter: hjfreyer
Source: Waterloo local 2000.09.23
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2560



Freckles is problem number 2560 on the Peking University ACM site.

I've only tested this on the sample input, but it seems to work fine.

This solution saves the input as a collection of vertices and inputs them into a min-heap organized by their distance from an arbitrarily chosen first vertex (the last one to be inputted). It then runs Prim's algorithm to find a minimum spanning tree of the vertices, considering each vertex to be potentially connected to each other vertex. Every time an edge is added to the tree, it's weight is added to the total weight of the tree. This value is the minimum amount of 'ink' needed to connect all of the dots.


Code

import java.util.*;
import java.io.*;

public class Main
{
	public static Scanner in;
	public static double inkCost;
	public static minHeap theHeap;
	
	public static void main(String[] asd)
	{
		
		in=new Scanner(System.in);
		
		theHeap = new minHeap();
		getVerts(in);
		doWork();
		System.out.printf("%.2f",inkCost);
	}
	
	public static void getVerts(Scanner in)
	//take the input and create a set of vertices
	{
		int numV = in.nextInt();
		for(int i = 0; i < numV; i++)
		{
			minHeap.insert(new vertex(in.nextDouble(), in.nextDouble()));
		}
		minHeap.findMin().dist = 0;
	}
	
	public static void doWork()
	{
		vertex v;
		while(!theHeap.isEmpty())
		{
			v = theHeap.deleteMin();
			v.visited = true;
			inkCost += v.dist;
			for(int i = 1; i <= theHeap.currentSize; i++)
			{
				vertex w = theHeap.array[i];
				if((w.dist > w.distTo(v))&& !w.visited)
				{
					w.dist =  w.distTo(v);
					theHeap.update();
				}
			}
		}
		
	}

}

/* Implementation of a minHeap of verteces
 * OPERATIONS:
 * insert(x)
 * deletemin()
 * isEmpty()
 * 
 * This code was modified from the BinaryHeap program  
 * Evan Korth's V.22.0102 Data Structures Fall 2006.
 */

class minHeap
{
	public static int currentSize;
	public static vertex[] array;
	
	public minHeap()
	{
		currentSize = 0;
		array = new vertex[101];
	}
	
	public static void insert(vertex v)
	{
		int hole = ++currentSize;
		for(; hole > 1 && v.dist < array[hole/2].dist; hole/=2)
			array[hole] = array[hole/2];
		array[hole] = v;
	}
	
	public static vertex findMin()
	{
		if(isEmpty())
				return null;
		else return array[1];
		
	}
	
	public static vertex deleteMin()
	{
		if(isEmpty())
			return null;
		
		vertex minItem = findMin();
		array[1] = array [currentSize--];
		percolateDown(1);
		return minItem;
	}
	
	
	public static boolean isEmpty()
	{
		return currentSize == 0;
	}
	
	private static void percolateDown(int hole)
	{
		int child;
		vertex tmp = array[hole];
		
		for(; hole *2 <= currentSize; hole = child)
		{
			child = hole*2;
			if(child  != currentSize && array[child+1].dist < array[child].dist)
				child++;
			if(array[child].dist <tmp.dist)
				array[hole] = array[child];
			else
				break;
		}
		array[hole] = tmp;
	}
	
	public static void update()
	{
		for(int i = currentSize; i>0; i--)
		{
			percolateDown(i);
		}
	}

}

class vertex {
    public boolean visited=false;
    public double dist;
    public double x;
    public double y;

    public vertex(){
    	dist = 100000;
     }
    public vertex(double xCoord, double yCoord)
    {
    	dist = 100000;
    	x = xCoord;
    	y = yCoord;
    }
    
    public double distTo(vertex w)
    {
    	double tmp = Math.abs(Math.abs(this.y - w.y)*Math.abs(this.y - w.y)+Math.abs(this.x - w.x)*Math.abs(this.x - w.x));
    	return Math.sqrt(tmp);
    }

}

Personal tools