學步園

從學習c++以來,第一次用類做acm題,值得紀念一下

#include<iostream>
using namespace std;
class rectangle
{
private:
    int x1,y1,x2,y2;
public:
    rectangle(){}
    rectangle(int a,int b,int c,int d)
    {
        x1=a;y1=b;x2=c;y2=d;
    }
    void inpoint(int a,int b,int c,int d)
    {
        x1=a;y1=b;
        x2=c;y2=d;
    }
    int getarea()
    {
        return (x2-x1)*(y2-y1);
    }
    friend rectangle produce_rec(rectangle a,rectangle b);
};
rectangle rec[21],subrec[21];
int maxv(int a,int b)
{
    return a>b?a:b;
}
int minv(int a,int b)
{
    return a>b?b:a;
}
rectangle produce_rec(rectangle a,rectangle b)
{
    rectangle p;
    if(a.x2<=b.x1||b.x2<=a.x1||a.y2<=b.y1||b.y2<=a.y1)
    {
        p.x1=p.y1=p.x2=p.y2=0;
    }
    else
    {
        p.x1=maxv(a.x1,b.x1);
        p.y1=maxv(a.y1,b.y1);
        p.x2=minv(a.x2,b.x2);
        p.y2=minv(a.y2,b.y2);
    }
    return p;
}
int dfs(int x,int t,rectangle cur)
{
    if(!cur.getarea())
        return 0;
    rectangle tmp;
    int ans=0;
    for(int i=x;i<t;i++)
    {
        tmp=produce_rec(cur,subrec[i]);
        ans+=tmp.getarea()-dfs(i+1,t,tmp);
    }
    return ans;
}
int main()
{
    int n,m,x1,y1,x2,y2,total,cnt=1;
    while(cin>>n>>m&&(n||m))
    {
        cout<<"Case "<<cnt++<<':'<<endl;
        for(int i=0;i<n;i++)
        {
            cin>>x1>>y1>>x2>>y2;
            rec[i].inpoint(x1,y1,x2,y2);
        }
        for(int i=0;i<m;i++)
        {
            cin>>total;
            for(int j=0;j<total;j++)
            {
                int d;
                cin>>d;
                subrec[j]=rec[d-1];
            }
            rectangle x(0,0,1000,1000);
            int ans=dfs(0,total,x);
            cout<<"Query "<<i+1<<": "<<ans<<endl;
        }
        cout<<endl;
    }
    return 0;
}