POJ 3695 Rectangles

POJ_3695

    一个直观的思路就是对每次Query求一次这些矩形面积的并，具体的思路可以参考我的POJ_1151的题解，那个题也是求矩形面积的并的。但这样耗时会比较长，我暂时还没想到太好的思路。

    http://www.cnblogs.com/staginner/archive/2012/02/20/2359396.html

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 50
struct rec
{
    int x1, y1, x2, y2;
}p[MAXD], res[MAXD];
int N, M, K, X, cnt, tx[MAXD], left[MAXD], right[MAXD];
int cmp1(const void *_p, const void *_q)
{
    rec *p = (rec *)_p, *q = (rec *)_q;
    return p->y1 - q->y1;
}
int cmp2(const void *_p, const void *_q)
{
    int *p = (int *)_p, *q = (int *)_q;
    return *p - *q;
}
void init()
{
    int i, j, k;
    for(i = 1; i <= N; i ++)
        scanf("%d%d%d%d", &p[i].x1, &p[i].y1, &p[i].x2, &p[i].y2);
}
void solve()
{
    int i, j, k, t, ans, up, down;
    for(t = 0; t < M; t ++)
    {
        ans = X = 0;
        scanf("%d", &K);
        for(i = j = 0; i < K; i ++)
        {
            scanf("%d", &k);
            res[i] = p[k];
            tx[j ++] = p[k].x1;
            tx[j ++] = p[k].x2;
        }
        qsort(res, K, sizeof(res[0]), cmp1);
        qsort(tx, j, sizeof(tx[0]), cmp2);
        for(i = 1; i < j; i ++)
            if(tx[i] != tx[i - 1])
            {
                left[X] = tx[i - 1], right[X] = tx[i];
                ++ X;
            }
        for(i = 0; i < X; i ++)
        {
            up = down = -1;
            for(j = 0; j < K; j ++)
                if(left[i] >= res[j].x1 && right[i] <= res[j].x2)
                {
                    if(res[j].y1 > up)
                    {
                        ans += (right[i] - left[i]) * (up - down);
                        down = res[j].y1, up = res[j].y2;
                    }
                    else if(res[j].y2 > up)
                        up = res[j].y2;
                }
            ans += (right[i] - left[i]) * (up - down);
        }
        printf("Query %d: %d\n", ++ cnt, ans);
    }
}
int main()
{
    int t = 0;
    for(;;)
    {
        scanf("%d%d", &N, &M);
        if(!N && !M)
            break;
        init();
        printf("Case %d:\n", ++ t);
        cnt = 0;
        solve();
        printf("\n");
    }
    return 0;
}