Poj Solution 2473

http://poj.org/problem?id=2473

#include<iostream>
#include"algorithm"
using namespace std;

struct rect
{
    int x1,x2,y1,y2;
}r[210];

int n,w,h,n1,n2,m;
int x[411],y[411];

void init()
{
    int i;
    cin>>n>>w>>h;
    for(i=0;i<n;i++)
    {
        cin>>r[i].x1>>r[i].y1>>r[i].x2>>r[i].y2;
        x[i]=r[i].x2;
        y[i]=r[i].y2;
    }

    m=n+1;
    x[n]=0,y[n]=0;

    std::sort(x,x+m);
    std::sort(y,y+m);
    n1=std::unique_copy(x,x+m,x)-x;
    n2=std::unique_copy(y,y+m,y)-y;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}

void doit()
{
    int ww,hh,i,j,k=0;
    
    cin>>ww>>hh;
    
    for(i=0;i<n1;i++)
    if(y[i]+hh<=h)
        for(j=0;j<n2;j++)
        {
            if(x[j]+ww<=w)
            {
                for(k=0;k<n;k++)
                if(min(r[k].x2,x[j]+ww)>max(r[k].x1,x[j])&&min(r[k].y2,y[i]+hh)>max(r[k].y1,y[i]))
                    break;
                if(k==n)
                    goto loop;
            }
        }
loop:
    if(i<n1)
        cout<<x[j]<<' '<<y[i]<<endl;
    else cout<<"Fail!"<<endl;
}

int main()
{
    int cas;
    cin>>cas;
    while(cas--)
    {
        init();
        doit();
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *