这是一道.. 怎么说呢 只能用龌龊来形容的题目..

折腾了两天, 重写了两遍, 第一次在题目里用链表, 有点为难自己的意思, 不过确实暂时还没想到其他可以省空间的办法.

思路:

1. 每一块用一个节点存储, 存储方式我用的点阵..   先随便找出一个点 然后dfs搜出这个点所在的区域

2. 每一块cake正过来反过来各转4个90度, 用从上到下从左到右一个点一个点比过去这样来排序, 有点傻不过还没发掘出什么具有[旋转不变性]的数学方法可以算出方向不同的cake的特征.

3. 选出8个方向(360度/90度*翻转的2面)最大的cake存储

细节:

1. 排序用qsort就很方便

2. 用了个format()把cake仅靠坐标系,这样sort()过后cake之间的比较是数组里元素一一对应的比较

刚刚好250行.. 不是说前两页1009是最恶心的吗..被骗了..

#include <iostream>
#include <string.h>
#include <stdlib.h>

using namespace std;

typedef struct coo {
    int x,y;
} Coo;

typedef struct cake {
    Coo a[10000];
    int n,amount;
    struct cake *next;
} Cake;

int t,n,w,h;
Coo a1[10000],a2[10000];
bool cherry[100][100];
Cake *newpiece,*a1cake,*a2cake;

int comp(const void *a,const void *b) {
    int t;
    if((t=(*(Coo *)a).y-(*(Coo *)b).y)!=0)
        return -t;
    return (*(Coo *)a).x-(*(Coo *)b).x;
}

void dfs_init(Coo *a) {
    for(int i=0;i<w;i++)
        for(int j=0;j<h;j++)
            cherry[i][j]=false;
    for(int i=0;i<n;i++)
        cherry[a[i].x][a[i].y]=true;
    return;
}

Cake *dfs() {
    Cake *bake;
    int m1,m2;
    bake=(Cake *)malloc(sizeof(Cake));
    bake->n=bake->amount=0;
    for(int i=0;i<w;i++)
        for(int j=0;j<h;j++)
            if(cherry[i][j]) {
                bake->a[0].x=i;
                bake->a[0].y=j;
                cherry[i][j]=false;
                bake->n++;
                i=w;
                break;
            }
    if(bake->n==0)
        return NULL;
    m1=0;
    m2=1;
    while(m1!=m2) {
        for(int i=-1;i<=1;i++)
            for(int j=-1;j<=1;j++) {
                if((i+j==1||i+j==-1)&& bake->a[m1].x+i>=0 && bake->a[m1].x+i<w &&
                bake->a[m1].y+j>=0 && bake->a[m1].y+j<h &&
                cherry[bake->a[m1].x+i][bake->a[m1].y+j]) {
                    bake->a[m2].x=bake->a[m1].x+i;
                    bake->a[m2].y=bake->a[m1].y+j;
                    m2++;
                    cherry[bake->a[m1].x+i][bake->a[m1].y+j]=false;
                }
            }
        m1++;
    }
    bake->n=m2;
    return bake;
}


//  This produces a new rotated cake
void rotate(Cake *&a) {
    int x;
    for(int i=0;i<a->n;i++) {
        x=a->a[i].x;
        a->a[i].x=a->a[i].y;
        a->a[i].y=-x;
    }
    return;
}
void roll(Cake *&a) {
    for(int i=0;i<a->n;i++)
        a->a[i].x*=-1;
    return;
}

void format(Cake *f) {
    Coo corner;
    qsort((void *)(f->a),f->n,sizeof(Coo),comp);
    corner=f->a[0];
    for(int i=1;i<f->n;i++)
        if(corner.x>f->a[i].x)
            corner.x=f->a[i].x;
    for(int i=0;i<f->n;i++) {
        f->a[i].x-=corner.x;
        f->a[i].y-=corner.y;
    }
    return;
}

// Cake p1 and p2 should have been sorted. otherwise can't do comparing
bool isBigger(Cake *p1,Cake *p2) {
    int t;
    for(int i=0;i<p1->n;i++) {
        t=comp((void *)(p1->a+i),(void *)(p2->a+i));
        if(t<0)
            return true;
        if(t>0)
            return false;
    }
    return false;
}

//always sort *newpiece.
void sort()
{
    Cake *tbc,*temp;    //The Biggest Cake =D
    tbc=newpiece;
    format(tbc);
    temp=(Cake *)malloc(sizeof(Cake));
    *temp=*tbc;
    for (int i=2;i<=8;i++) {
        if(i==5)
            roll(temp);
        else
            rotate(temp);
        format(temp);
        if(isBigger(temp,tbc)) {
            *tbc=*temp;
        }
    }
    free(temp);
    newpiece=tbc;
}

/*  isCakeALie: Search matched cake in the list.
    Input:      global variable *a1cake and *newpiece
    Output:     If there is a match, output a pointer to the cake(in the list), otherwise
                return NULL;    */
Cake *isCakeALie() {
    int i;
    Cake *p;
    p=a1cake;
    while(p) {
        if(p->n==newpiece->n) {
            for(i=0;i<p->n;i++)
                if(p->a[i].x!=newpiece->a[i].x||p->a[i].y!=newpiece->a[i].y)
                    break;
            if(i==p->n)
                break;
        }
        p=p->next;
    }
    return p;
}

//seal newpiece into a1cake
void seal() {
    Cake *pos;
    if(pos=isCakeALie()) {
        pos->amount++;
        free(newpiece);
        return;
    }
    pos=a1cake;
    a1cake=newpiece;
    newpiece->next=pos;
    a1cake->amount=1;
    return;
}

//eat one cake at one time in *a1cake
bool fuck() {
    Cake *pos,*temp;
    pos=isCakeALie();
    free(newpiece);
    if(pos==NULL)
        return false;
    if(pos->amount==1) {
        if(a1cake==pos) {
            a1cake=a1cake->next;
            free(pos);
            return true;
        }
        for(temp=a1cake;temp->next!=pos;temp=temp->next);
        temp->next=pos->next;
        free(pos);
        return true;
    }
    pos->amount--;
    return true;
}



int main()
{
    bool okay;
    Cake *temp;
    cin>>t;
    while (t--) {
        cin>>w>>h>>n;
        for (int i=0;i<n;i++)
            cin>>a1[i].x>>a1[i].y;
        for (int i=0;i<n;i++)
            cin>>a2[i].x>>a2[i].y;

        a1cake=NULL;
        dfs_init(a1);
        while (1) {
            newpiece=dfs();
            if (!newpiece)
                break;
            sort();
            seal();
        }

        dfs_init(a2);
        okay=true;
        while (1) {
            newpiece=dfs();
            if (!newpiece)
                break;
            sort();
            if (!fuck()) {
                okay=false;
                free(newpiece);
                break;
            }
            //free(newpiece);       Do it inside fuck()
        }
        if (a1cake)
            okay=false;
        if (okay)
            cout<<"YES\n";
        else
            cout<<"NO\n";
        while(a1cake) {
            temp=a1cake;
            a1cake=a1cake->next;
            free(temp);
        }
    }
    return 0;
}