Problem $2.$ The gold mining company Gold$336$ wants to buy a lot of land. It has a list of available

lots LOTS. Each lot $i$ is an axis$-$parallel rectangle with coordinates LOTS $[i].x1,$LOTS$[i].x2,$LOTS$[i]*y1,$

LOTS $[i].y2.$ The cost of the lot is LOTS $i.$cost$.$ The company also has a list of gold mines GOLDMINES.

Mine $j$ has coordinates goldMines $[j].x$ and GOLDMines $[j].y$ and value GoldMines $j.$value. The

total revenue that Gold$336$ can get from lot i equals the sum of values of gold mines located on

the property $($boundaries are included$).$ The profit from the lot equals the revenue from that lot

minus its cost. Your goal is to design an algorithm that finds the best lot. Lots do not overlap, i$.$e$.$

they are disjoint rectangles. Lots are non$-$degenerate rectangles, meaning lots $[i].y1<[i].y22*{10}^{5}2*{10}^9[i].x1$ and

lots $[i].y1<$ lots $[i].y2.$ There might $be$ multiple gold mines $in$ the same location.

Please, design $an$ algorithm for this problem. Implement the following function.

long long int FindBestLot$(const$ vector& lots,

const vector& goldMines$)$

The function should return the profit $of$ the most profitable lot. The parameters are $as$ follows: lots

$is$ the list $of$ lots; goldMines $is$ the list $of$ gold mines.

Submission The instructions are similar $to$ the previous homeworks. Your program must pass

each test $inno$ more than $1$ second. You can assume that the number $of$ lots and the number $of$

gold mines $isat$ most $2*{10}^5,$ and $at$ least one lot exists. All other numbers are between $0$ and $2*{10}^9$

$.$#include

using std::vector;

struct Lot $\{$

int x$1,$ y$1$;

int x$2,$ y$2$;

int cost;

Lot$($int x$1,$ int y$1,$ int x$2,$ int y$2,$ int cost$)$: x$1($x$1),$ y$1($y$1),$ x$2($x$2),$ y$2($y$2),$ cost$($cost$)\{\}$

$\}$;

struct GoldMine $\{$

int x$,$ y;

int value;

GoldMine$($int x$,$ int y$,$ int value$)$: x$($x$),$ y$($y$),$ value$($value$)\{\}$

$\}$;

long long int FindBestLot$($const vector& lots, const vector& goldMines$)\{$

$\}$