Trash Removal

It seems clear that the first thing to do is to take the convex hull, since the non-convex portions of the shape can't possibly affect the solution. Then the solution will involve one side of the hull flat against one wall, and at least one vertex of the hull against the opposite wall. You can prove this pretty simply by taking a right triangle flat against the wall and the other leg going from the flat wall side to the point on the other side and see that rotating it slightly must yield an increase in distance.

Anyway, solution is to iterate over all sides with the hull and calculate the furthest point away from that edge (have to know point line distance!). Then taking the side with the minimum distance to the further point.

Runtime: O(nlogn) for the hull, and O(n^2) for the walk. This is all you need to be fast enough. The second part can be done in O(n) time if we caterpillar walk the edge and vertices, since we know as we increment one edge, the new furthest point can't be behind the furthest point of the previous edge. So we examine each edge and vertex at most twice.

We can also solve this without taking the hull by taking any two pairs of points and computing the maximum difference in signed distance from the line to any other vertex, and then selecting the minimum of those. You can also caterpillar walk this, giving you O(n) run time overall.

import java.util.*;
import java.awt.*;
import java.awt.geom.Line2D;
public class k {

	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new k().go();
	}
	private void go() {
		int on=0;
		while(true){
			on++;
			int n=in.nextInt();
			if(n==0)break;
			ArrayList<Point> p=new ArrayList<Point>();
			for(int i=0;i<n;i++)p.add(new Point(in.nextInt(),in.nextInt()));
			p=hull(p);
			double min=Double.MAX_VALUE;
			for(int i=0;i<p.size();i++){
				double max=0;
				for(int j=i+2;j%p.size()!=i;j++){
					j%=p.size();
					Line2D.Double temp=new Line2D.Double(p.get(i), p.get((i+1)%p.size()));
					if(temp.ptLineDist(p.get(j))>max)max=temp.ptLineDist(p.get(j));
				}
				if(max<min)min=max;
			}
			System.out.printf("Case %d: %.2f\n", on, min);
		}
	}
	public ArrayList<Point> hull(ArrayList<Point> in){
		ArrayList<Point> out=new ArrayList<Point>();
		Point temp=new Point(0,Integer.MAX_VALUE);
		for(Point p:in)if(p.y<temp.y||(p.y==temp.y&&p.x<temp.x))temp=p;
		final Point min=new Point(temp);
		PriorityQueue<Point> pq=new PriorityQueue<Point>(in.size(), new Comparator<Point>(){
			public int compare(Point p0, Point p1) {
				if(Math.atan2(p0.y-min.y,p0.x-min.x)-Math.atan2(p1.y-min.y,p1.x-min.x)>0)return 1;
				return -1;
			}
		});
		out.add(min);
		for(Point p:in)if(!p.equals(temp))pq.offer(p);
		while(!pq.isEmpty()){
			if(out.size()<2)out.add(pq.poll());
			double cp=(out.get(out.size()-1).x-out.get(out.size()-2).x)*(pq.peek().y-out.get(out.size()-1).y)-(pq.peek().x-out.get(out.size()-1).x)*(out.get(out.size()-1).y-out.get(out.size()-2).y);
			double d=out.get(out.size()-2).distance(pq.peek())-out.get(out.size()-2).distance(out.get(out.size()-1));
			if(cp==0){
				if(d<0)pq.poll();
				else out.remove(out.size()-1);
			}else{
				if(cp>0)out.add(pq.poll());
				else out.remove(out.size()-1);
			}
		}
		if((out.get(out.size()-1).x-out.get(out.size()-2).x)*(out.get(0).y-out.get(out.size()-1).y)-(out.get(0).x-out.get(out.size()-1).x)*(out.get(out.size()-1).y-out.get(out.size()-2).y)==0)out.remove(out.size()-1);
		return out;
	}
}
//Trash Removal
//hull
//cross product

This is the same problem as Playing the Slots, but that edition has floats instead of integers for coordinates.