Aquarium Tank

Introduction

This asks you to take an input convex prism and fill it with some volume of water, determining how high the top of the water reaches

Solutions

Iterative

Once you have determined which points are on the right and left hand sides, fill the water up to the LOWEST vertex on either the left or right hand side. Determine the x,y coordinate on the other side that the water is at (some basic geometry), and subtract the volume of this region (trapezoid area * depth) from the water left. Bump the lowest vertex we used to the next highest on that side and repeat until either we've reached the top or all water is used.

Note that we may not completely fill up a region with water. In this case, we must take the remaining volume of water and calculate the height it reaches in the given trapezoidal region. After algebra-ing, we find that this is a quadratic function in h, so we must plug in the quadratic formula and take the positive zero.

Gotchas

• Input of the polygon may start anywhere, not necessarily at the base
• Vertices on the left and right side might be at the same height, so ensure we handle this case
• we may have more than enough water to fill the entire tank
• When computing the last, not-completely-filled region, it may be a parallelogram, causing the quadratic formula to divide by 0.

Code

Solution - Java

import java.util.*;
public class g {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new g().go();
	}
	private void go() {
		int n=in.nextInt(),d=in.nextInt();
		double l=in.nextDouble()*1000/d;
		int[][] p=new int[n][2];
		for(int i=0;i<n;i++){
			p[i][0]=in.nextInt();
			p[i][1]=in.nextInt();
		}
		int[] c=new int[2];
		for(int i=0;i<n;i++){//find bottom left and top right
			if(p[i][1]==0&&p[(i+1)%n][1]==0)c[0]=i;
			if(p[i][1]!=0&&p[(i+1)%n][1]==p[i][1])c[1]=i;
		}
		int curl=c[0],curr=(c[0]+1)%n;
		double[] base={p[curl][0],p[curr][0],p[curr][1]};//x0,x1,h of current water level
		curl=(curl-1+n)%n;//candidate next fill points
		curr=(curr+1)%n;
		while(l!=0&&curl!=c[1]){//stop when we're out of water or we've reached the top
			if(p[curl][1]<p[curr][1]){
				double h=p[curl][1]-base[2];
				double nextr=base[1]+(p[curr][0]-base[1])*h/(p[curr][1]-base[2]);
				double a=h*(nextr-p[curl][0]+base[1]-base[0])/2;
				if(a<l){
					l-=a;
					base[0]=p[curl][0];
					base[1]=nextr;
					base[2]=base[2]+h;
					curl=(curl-1+n)%n;
				} else {
					base[2]=base[2]+quad(l,base[1]-base[0],h,nextr-base[1],p[curl][0]-base[0]);
					l=0;
				}
			} else if(p[curl][1]>p[curr][1]){
				double h=p[curr][1]-base[2];
				double nextl=base[0]+(p[curl][0]-base[0])*h/(p[curl][1]-base[2]);
				double a=h*(p[curr][0]-nextl+base[1]-base[0])/2;
				if(a<l){
					l-=a;
					base[0]=nextl;
					base[1]=p[curr][0];
					base[2]=base[2]+h;
					curr=(curr+1)%n;
				} else {
					base[2]=base[2]+quad(l,base[1]-base[0],h,p[curr][0]-base[1],nextl-base[0]);
					l=0;
				}
			} else {
				double a=(p[curr][1]-base[2])*(p[curr][0]-p[curl][0]+base[1]-base[0])/2;
				if(a<l){
					l-=a;
					base[0]=p[curl][0];
					base[1]=p[curr][0];
					base[2]=p[curr][1];
					curl=(curl-1+n)%n;
					curr=(curr+1)%n;
				} else {
					base[2]=base[2]+quad(l,base[1]-base[0],p[curr][1]-base[2],p[curr][0]-base[1],p[curl][0]-base[0]);
					l=0;
				}
			}
		}
		System.out.printf("%.2f\n",base[2]);
	}
	private double quad(double area, double bottom_base, double height, double right_offset, double left_offset) {//given a trapezoid and an area, computes how high up to go
		if(right_offset == left_offset)return height*area/((bottom_base+bottom_base+right_offset-left_offset)/2*height);//actually a parallelogram
		double a=right_offset/height-left_offset/height;
		double b=2*bottom_base;
		double c=-2*area;
		double z1=(-1*b+Math.sqrt(b*b-4*a*c))/2/a;
		return z1;
	}
}