Cod sursa(job #573526)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 6 aprilie 2011 12:45:11
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.57 kb
// infoarena: problema/dr //
#include <fstream>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;

ifstream in("date.in");
ofstream out("date.out");

const int MAXX = 10010;
const int MAXN = 1010;

struct punct
{
    int x,y;
    punct(){}
    punct(int _x, int _y)
    {
        x = _x;
        y = _y;
    }
};

struct cmp
{
    inline bool operator()(punct a, punct b)
    {
        if(a.x != b.x)
            return (a.x < b.x);
        return (a.y < b.y);
    }
};

struct drept
{
    int x1,y1,x2,y2,v;
    drept(){}
    drept(int _x1, int _y1, int _x2, int _y2)
    {
        x1 = _x1;
        x2 = _x2;
        y1 = _y1;
        y2 = _y2;
    }
};

punct p[MAXN];
short a[220000000];
int n,i,j,xm,ym,t,M;

inline void insert(int i, int x1=1, int y1=1, int x2=xm, int y2=ym, int k=1)
{
    if(x1 > x2 || y1 > y2)
        return;
    if(x1 <= p[i].x && p[i].x <= x2 && y1 <= p[i].y && p[i].y <= y2)
    {
        a[k] = i;
        if(x1 == x2 && y1 == y2)
            return;
        insert(i, x1, y1, (x1+x2)/2, (y1+y2)/2, 4*k);
        insert(i, x1, (y1+y2)/2+1, (x1+x2)/2, y2, 4*k+1);
        insert(i, (x1+x2)/2+1, y1, x2, (y1+y2)/2, 4*k+2);
        insert(i, (x1+x2)/2+1, (y1+y2)/2+1, x2, y2, 4*k+3);
    }
}

inline int query(int xx1, int yy1, int xx2, int yy2, int x1=1, int y1=1, int x2=xm, int y2=ym, int k=1)
{
    if(a[k] == 0)
        return 0;
    if(x1 > x2 || y1 > y2)
        return 0;
    if(xx1 > x2 || xx2 < x1 || yy1 > y2 || yy2 < y1)
        return 0;
    if(xx1 >= x1 && xx2 <= x2 && yy1 >= y1 && yy2 <= y2)
        return a[k];
    int a = query(xx1, yy1, xx2, yy2, x1, y1, (x1+x2)/2, (y1+y2)/2, 4*k),
        b = query(xx1, yy1, xx2, yy2, x1, (y1+y2)/2, (x1+x2)/2+1, y2, 4*k+1),
        c = query(xx1, yy1, xx2, yy2, (x1+x2)/2+1, y1, x2, (y1+y2)/2, 4*k+2),
        d = query(xx1, yy1, xx2, yy2, (x1+x2)/2+1, (y1+y2)/2+1, x2, y2, 4*k+3);
    return max(max(a,b), max(c,d));
}

inline punct search(int x1, int y1, int x2, int y2, int li=1, int ls=n)
{
    int q = query(x1, y1, x2, y2);
    if(!q)
        return punct(-1, -1);
    return p[q];

    /*int i;
    for(i=1; i<=n; i++)
        if(p[i].x > x1 && p[i].x < x2 &&
           p[i].y > y1 && p[i].y < y2)
            return p[i];
    return punct(-1, -1);*/

    /*if(li > ls)
        return punct(-1, -1);

    if(p[(li+ls)/2].x > x1 && p[(li+ls)/2].x < x2 &&
       p[(li+ls)/2].y > y1 && p[(li+ls)/2].y < y2)
        return p[(li+ls)/2];
    if(p[(li+ls)/2].x > x1 && p[(li+ls)/2].x < x2)
    {
        int i;
        for(i=li; i<=ls; i++)
            if(p[i].x > x1 && p[i].x < x2 &&
               p[i].y > y1 && p[i].y < y2)
                return p[i];
        return punct(-1, -1);
    }
    else
        if(p[(li+ls)/2].x < x1)
            return search(x1, y1, x2, y2, li, (li+ls)/2-1);
        else
            return search(x1, y1, x2, y2, (li+ls)/2+1, ls);*/
}

inline void solve(int x1, int y1, int x2, int y2)
{
    if((x2-x1)*(y2-y1) <= M)
        return;
    punct k = search(x1, y1, x2, y2);
    if(k.x == -1)
    {
        M = (x2-x1)*(y2-y1);
        //out<<x1-1<<' '<<y1-1<<' '<<x2-1<<' '<<y2-1<<'\n';
        return;
    }
    solve(x1, y1, k.x, y2);
    solve(k.x, y1, x2, y2);
    solve(x1, y1, x2, k.y);
    solve(x1, k.y, x2, y2);
}

int main()
{
    in>>t;
    while(t--)
    {
        in>>n>>xm>>ym;

        memset(a, 0, sizeof(a));
        for(i=1; i<=n; i++)
        {
            in>>p[i].x>>p[i].y;
            p[i].x ++;
            p[i].y ++;
            insert(i);
        }

        //sort(p+1, p+n+1, cmp());

        M = 0;
        solve(1, 1, xm+1, ym+1);
        out<<M<<'\n';
    }
    return 0;
}