2014
01-26

# Slides

There are N slides lying on the table. Each of them is transparent and formed as a rectangle. In a traditional problem, one may have to calculate the intersecting area of these N slides. The definition of intersection area is such area which belongs to all of the slides.
But this time I want to take out some one of the N slides, so that the intersecting area of the left N-1 slides should be maximal. Tell me the maximum answer.

The first line of the input contains a single integer T, the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer N (1 <= N <= 100000), the number of rectangles. Followed by N lines, each line contains four integers x1, y1, x2, y2 (-10000 <= x1 < x2 <= 10000, -10000 <= y1 < y2 <= 10000), pair (x1, y1) gives out the bottom-left corner and pair (x2, y2) gives out the top-right corner of the rectangle.

The first line of the input contains a single integer T, the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer N (1 <= N <= 100000), the number of rectangles. Followed by N lines, each line contains four integers x1, y1, x2, y2 (-10000 <= x1 < x2 <= 10000, -10000 <= y1 < y2 <= 10000), pair (x1, y1) gives out the bottom-left corner and pair (x2, y2) gives out the top-right corner of the rectangle.

2
2
0 0 2 2
1 1 2 2
3
0 0 2 2
1 0 3 2
1 1 3 3

4
2

/**********************************************************

**********************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=100010;
const int L=-1000001;
const int R=1000001;

int x1[N], x2[N], y1[N], y2[N];

int main()
{
int tcase;
while (~scanf("%d",&tcase))
{
while (tcase--)
{
int n;
scanf("%d", &n);

int lx = L, ly = L, rx = R, ry = R;
int lx1 = L, ly1 = L, rx1 = R, ry1 = R;

for (int i = 0; i < n; i++)
{
scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
if (x1[i] > lx)
{
lx1 = lx;
lx = x1[i];
}
else if (x1[i] > lx1)
lx1 = x1[i];

if (y1[i] > ly)
{
ly1 = ly;
ly = y1[i];
}
else if (y1[i] > ly1)
ly1 = y1[i];

if (x2[i] < rx)
{
rx1 = rx;
rx = x2[i];
}
else if (x2[i] < rx1)
rx1 = x2[i];

if (y2[i] < ry)
{
ry1 = ry;
ry = y2[i];
}
else if (y2[i] < ry1)
ry1 = y2[i];
}

if (n==1)
{
printf("0\n");
continue;
}

int ans = 0;
int x,y;
int xx,yy;
for (int i = 0; i < n; i++)
{
if (x1[i] == lx)
x = lx1;
else
x = lx;

if (y1[i] == ly)
y = ly1;
else
y = ly;

if (x2[i] == rx)
xx = rx1;
else
xx = rx;

if (y2[i] == ry)
yy = ry1;
else
yy = ry;

if (yy > y && xx > x)
{
int tmp = (yy - y)*(xx - x);
if (tmp > ans)
ans = tmp;
}
}

printf("%d\n",ans);
}
}
return 0;
}

1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

2. 代码是给出了，但是解析的也太不清晰了吧！如 13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)，为什么要这样拆分，原则是什么？