2013
11-09

# Rectangles

A specialist in VLSI design testing must decide if there are some components that cover each other for a given design. A component is represented as a rectangle. Assume that each rectangle is rectilinearly oriented (sides parallel to the x and y axis), so that the representation of a rectangle consists of its minimum and maximum x and y coordinates.

Write a program that counts the rectangles that are entirely covered by another rectangle.

The input contains the text description of several sets of rectangles. The specification of a set consists of the number of rectangles in the set and the list of rectangles given by the minimum and maximum x and y coordinates separated by white spaces, in the format:

nr_rectangles

xmin1 xmax1 ymin1 ymax1

xmin2 xmax2 ymin2 ymax2

xminn xmaxn yminn ymaxn

For each set,there will be less than 5000 rectangles.

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the number of rectangles that are covered).

3
100 101 100 101
0 3 0 101
20 40 10 400
4
10 20 10 20
10 20 10 20
10 20 10 20
10 20 10 20

0
4

//* @author  mekarlos@gmail.com
import java.util.Scanner;
public class Main {

public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=0,k=0;
boolean band;
int M[][]=new int[5000][4];
while(scan.hasNext()){
n=scan.nextInt();
for(int i=0;i< n;i++){
for(int j=0;j< 4;j++){
M[i][j]=scan.nextInt();
}
}
k=0;
for(int i=0;i< n;i++){
band=false;
for(int j=0;j< n;j++){
if(j!=i&&M[j][0]<=M[i][0]&&M[j][1]>=M[i][1]&&M[j][2]<=M[i][2]&&M[j][3]>=M[i][3]){
band=true;
break;
}
}
if(band)k++;
}
System.out.println(k);
}
}
}

1. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.

2. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;