Before revision:  We further propose an sampling algorithm with runtime O(n+poly(n, t, 1/\epsilon)), which with high probability finds a parallelogram covering at least (1-\epsilon)(n-t ) and at most (n-t+1 ) points with at most the exact optimal area.
After revision:  We further propose an sampling algorithm with runtime O(n+poly(n, t, 1/\epsilon)), which with high probability finds a rectangle covering at least (1-\epsilon)(n-t ) and at most (n-t+1 ) points with at most the exact optimal area.