首页 > ACM题库 > HDU-杭电 > hdu 2478 Slides-线段树-[解题报告]C++
2014
01-26

hdu 2478 Slides-线段树-[解题报告]C++

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

/**********************************************************
题意:
给出n个矩形,从里面抽掉一个,求剩下的所有矩形的面积交;

算法:
由于数据量不超过100000,所以不需要用线段树优化,只需要O(n)预处理就行了;
即从左往右处理[1,i]之间的矩形的面积交;
再从右往左也处理一次[i,n]的面积交;
然后枚举中间抽掉的矩形;
最后求一次左右两边的面积交就OK了;
**********************************************************/
#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()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
    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;
}

 

解题转自:http://blog.csdn.net/jarily/article/details/8441005


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

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