Programming Contest: Lawn
Description
This problem gives you a series of information about a lawn, including the outer area, the home, and areas that don’t need to be fertilize. Your objective is to find the area of the lawn that needs to be fertilized, and then say how many bags of the fertilizer are necessary. The heart of this algorithm is getting the area of a polygon (convex or concave).
[ complete description ] [ lawn.java ]
Sample Input
4 0 0 100 0 100 100 0 100
4 20 20 80 20 80 80 20 80
1
4 20 10 30 10 30 20 20 20
4 50 50 250 50 250 200 50 200
6 100 100 150 100 150 150 200 150 200 200 100 200
2
5 50 50 70 50 70 60 60 70 50 70
4 150 100 250 100 250 120 150 120
4 0 0 1 0 1 1 0 1
4 0 0 1 0 1 1 0 1
0
4 0 0 500 0 500 500 0 500
4 100 100 400 100 400 400 100 400
8
4 0 0 100 0 100 250 0 250
4 0 250 100 250 100 500 0 500
4 100 0 250 0 250 100 100 100
4 250 0 400 0 400 100 250 100
4 400 0 500 0 500 250 400 250
4 400 250 500 250 500 500 400 500
4 100 400 250 400 250 500 100 500
4 250 400 400 400 400 500 250 500
4 500 500 2500 500 2500 2500 500 2500
4 1000 1500 1500 1000 2000 1500 1500 2000
4
3 500 500 1000 500 500 1000
3 2000 500 2500 500 2500 1000
3 500 2500 500 2000 1000 2500
3 2000 2500 2500 2000 2500 2500
8 0 0 100 50 200 0 150 100 200 200 100 150 0 200 50 100
8 100 75 110 90 125 100 110 110 100 125 90 110 75 100 90 90
4
3 50 100 100 150 25 175
3 150 100 175 175 100 150
3 50 100 25 25 100 50
3 100 50 175 25 150 100
10 0 0 200 50 150 75 300 50 400 150 600 300 500 800 400 500 200 700 0 900
8 50 50 300 200 380 180 400 350 360 500 300 400 200 550 250 300
1
4 20 200 120 200 220 300 120 300
0
Sample Output
Lawn #1: buy 7 bag(s)
Lawn #2: buy 21 bag(s)
Lawn #3: buy 0 bag(s)
Lawn #4: buy 0 bag(s)
Lawn #5: buy 3000 bag(s)
Lawn #6: buy 9 bag(s)
Lawn #7: buy 271 bag(s)
Solution
// gets the area of a polygon (convex or concave)
public double polyarea(int poly[])
{
double total = 0.0;
for (int i=0; i<poly.length; i+=2)
{
int ii = (i+2) % (poly.length);
total += poly[i] * poly[ii+1] - poly[ii] * poly[i+1] ;
}
return Math.abs(total / 2.0) ;
}
public void go() throws Exception
{
Scanner in = new Scanner(new File("lawn.in"));
int n = in.nextInt(), count = 1, numbags = 0;
while(n!=0)
{
int lot[] = new int[2*n];
for(int i=0; i<lot.length; i++)
{
lot[i] = in.nextInt();
}
int house[] = new int[2*in.nextInt()];
for(int i=0; i<house.length; i++)
{
house[i] = in.nextInt();
}
n = in.nextInt();
int beds[][] = new int[n][];
for(int i=0; i<beds.length; i++)
{
beds[i] = new int[2*in.nextInt()];
for(int j=0; j<beds[i].length; j++)
{
beds[i][j] = in.nextInt();
}
}
// solve
double area = polyarea(lot);
area -= polyarea(house);
for(int i=0; i<beds.length; i++)
area -= polyarea(beds[i]);
numbags = (int)Math.ceil(area/1000);
// print
System.out.println("Lawn #"+count+": buy "+numbags+" bags(s)n");
// next
n = in.nextInt();
count++;
}
}