2012b_88que1

/*--------------------PART A-----------------------*/
    public static Rectangle smallestRect1(Point[] p)
    {
        Point sw = p[0];//south-west vertex
        int biggestX = p[0].getX();
        int biggestY = p[0].getY();
        for(int i = 1; i < p.length; i++){
            if(p[i].getX() < sw.getX() || p[i].getY() < sw.getY())
                sw = p[i];
            if(p[i].getX() > biggestX)
                biggestX = p[i].getX();
            if(p[i].getY() > biggestY)
                biggestY = p[i].getY();
        }
        Rectangle res = new Rectangle(biggestX - sw.getX(), biggestY - sw.getY(), sw);
        return res;
    }
/*--------------------PART B-----------------------*/
    public static Rectangle smallestRect2(Point[] p)
    {
        if(p.length == 1)
            return new Rectangle(0, 0, p[0]);
        int width = p[p.length - 1].getY() - p[0].getY();
        int high = p.length - 1, low = 0;
        int mid = 0;
        boolean found = false;
        while(low <= high && !found){
            mid = (high + low) / 2;
            if(p[mid].getY() == p[p.length - 1].getY()){
                if(p[mid - 1].getY() == p[0].getY())
                found = true;
                else
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
        int smallestX = Math.min(p[0].getX(), p[mid].getX());
        int biggestX = Math.max(p[p.length - 1].getX(), p[mid - 1].getX());
        Point sw = new Point(smallestX, p[0].getY());
        return new Rectangle(biggestX - smallestX, width, new Point(smallestX, p[0].getY()));
    }