Consider any four points $ABCD$ inside. If there is another point $E$ whose distance to $AC$ is more than from $B$ to $AC$, then move point $B$ to $E$. Keep doing this until no such point exists (also do it for the diagonal $BD$). Now consider 4 more points $A'B'C'D'$ such that $A$ is on $A'D'$, $B$ is on $A'B'$, $C$ is on $B'C'$, $D$ is on $C'D'$ and $D'A'\parallel BD\parallel B'C'$ and $A'B'\parallel AC\parallel C'D'$. Now if a vertex is outside $A'B'C'D'$, WLOG above $A'D'$, then it is a contradiction since we can move $A$ to that point. So every vertex is now inside $A'B'C'D'$ and the area of $ABCD$ is half than that of $A'B'C'D'$, which is more than the polygon itself.

Kind of a solution? You just gotta like, think about it. Let $A$ and $B$ be vertices of the polygon that maximizes length $AB$. If segment $\overline{AB}$ divides the polygon into two parts, then let $C$ and $D$ be the farthest vertices in the first and second parts, respectively, from $\overline{AB}$. One can show, using the method of contradiction, that the first part is contained entirely within the rectangle with side $\overline{AB}$ with opposite side passing through $C$, and that the second part is contained entirely within the rectangle with side $\overline{AB}$ with opposite side passing through $D$ (the details are left as an exercise for the reader). $\{A,C,B,D\}$ can thus trivially be shown to work. It's pretty much the same thing if $\overline{AB}$ is a side of the polygon instead of a diagonal.