Algorithm
Problem link- https://www.spoj.com/problems/DEFKIN/
DEFKIN - Defense of a Kingdom
Theodore implements a new strategy game “Defense of a Kingdom”. On each level a player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column.
The penalty of the position is the number of cells in the largest undefended rectangle. For example, the position shown on the picture has penalty 12.
Help Theodore write a program that calculates the penalty of the given position.
Input
The first line of the input file contains the number of test cases.
Each test case consists of a line with three integer numbers: w — width of the grid, h — height of the grid and n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).
Each of the following n lines contains two integer numbers xi and yi — the coordinates of the cell occupied by a tower (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).
Output
For each test case, output a single integer number — the number of cells in the largest rectangle that is not defended by the towers.
Example
Input: 1 15 8 3 3 8 11 2 8 6 Output: 12
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
T = int(input())
for c in range(T):
w, h, n = map(int, input().split(' '))
if n == 0:
print(w * h)
continue
rows, columns = [], []
for i in range(n):
x, y = map(int, input().split(' '))
rows.append(x)
columns.append(y)
rows.sort()
columns.sort()
l = max(rows[0] - 1, w - rows[n - 1])
r = max(columns[0] - 1, h - columns[n - 1])
for i in range(1, n):
l = max(l, rows[i] - rows[i - 1] - 1)
r = max(r, columns[i] - columns[i - 1] - 1)
print(l * r)Input
15 8 3
3 8
11 2
8 6
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h7gt;
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i < n; i++)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>b;i--)
#define forit(it,x) for (auto it=(x).begin();it!=(x).end(); it++)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sll set<ll>
#define vll vector<ll>
#define msl map<string,ll>
#define mll map<ll,ll>
ll i, j, k;
int main()
{
ll t=1;
cin >> t;
while(t--)
{
ll w, h, n;
cin >> w >> h >> n;
if(n == 0)
{
cout << w * h << endl;
continue;
}
ll width[n], height[n], max1=0 , max2 = 0;
for (i = 0; i < n;i++)
{
cin >> width[i] >> height[i];
}
sort(width, width + n);
sort(height, height + n);
for (i = 1; i < n; i++)
{
max1 = max(max1, width[i] - width[i - 1] -1);
max2 = max(max2, height[i] - height[i - 1] -1);
// cout << max1 << " " << max2 << endl;
}
max1 = max(max1, width[0] -1 );
max1 = max(max1, w - width[n-1]);
max2 = max(max2, height[0] - 1);
max2 = max(max2, h- height[n-1]);
cout << max1 * max2 << endl;
}
// cout << endl << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
} Input
15 8 3
3 8
11 2
8 6
Output
Demonstration
SPOJ Solution-Defense of a Kingdom-Solution in C, C++, Java, Python