Window Area[USACO]

本是古典何须时尚 2021-11-16 12:08 257阅读 0赞

用线性表实现的。算覆盖面积的时候，每次从当前矩形向后扫描最多被后一个矩形分成n1（n1<=4）个小的矩形，然后这n个小的矩形再分别计算被下下个矩形覆盖后形成了n2个新的矩形...

开始把b 和 t 的操作给搞反了，还有就是定义的nTop 先把它往纵坐标理解的，写着写着突然脑抽了一下，把它当行号给理解了。结果关于top的判断就错了一半...。

第4次才提交通过.

/*
    ID: zhangyc1
    LANG: C++
    TASK: window
    */
    #include <string>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <cmath>
    #include <queue>
    using namespace std;
    
    struct SRectangle
    {
        int nLeft, nRight, nTop, nBottom;
        SRectangle(){}
        SRectangle(int xl, int xr, int yt, int yb):nLeft(xl),nRight(xr),nTop(yt),nBottom(yb){}
    };
    struct SRectangleEx : SRectangle
    {
        int nID;
        SRectangleEx(int n):nID(n){}
    };
    
    struct SLink;
    SLink *pHead = NULL, *pTail = NULL;
    struct SLink
    {
        SRectangleEx* pRect;
        SLink *pNext, *pPre;
        SLink(SRectangleEx* p):pRect(p), pPre(pTail), pNext(NULL){}
    };
    
    SLink* arrLinkAdd[100];
    char chAct, chID;
    int nX1, nX2, nY1, nY2;
    SLink** ppLink = &pHead;
    
    inline void swap (int &a, int &b){ int temp = a; a = b; b = temp;}
    
    void RemoveLink(SLink* pLink)
    {
        if (pLink->pPre)
            pLink->pPre->pNext = pLink->pNext;
        else
            pHead = pLink->pNext;
    
        if (pLink->pNext)
            pLink->pNext->pPre = pLink->pPre;
        else
            pTail = pLink->pPre;
        pLink->pNext = NULL;
        pLink->pPre = NULL;
    }
    
    void prepairData()
    {
        char buf[100];
        int nID;
        while (scanf("%c(%c", &chAct, &chID) > 0)
        {
            nID = chID - '0';
            switch (chAct)
            {
            case 'w':
                {
                    SRectangleEx* pRect = new SRectangleEx(nID);
                    scanf(",%d,%d,%d,%d",&pRect->nLeft,&pRect->nTop,&pRect->nRight,&pRect->nBottom);
                    if (pRect->nLeft > pRect->nRight) swap(pRect->nLeft, pRect->nRight);
                    if (pRect->nTop < pRect->nBottom) swap(pRect->nTop, pRect->nBottom);
                    SLink* pLink = new SLink(pRect);
                    arrLinkAdd[nID] = pLink; // 索引矩形
                    *ppLink = pLink; // 链入尾部
                    ppLink = &pLink->pNext;
                    pTail = pLink;
                }
                break;
            case 'b':
                {
                    SLink* pLink = arrLinkAdd[nID];
                    RemoveLink(pLink);
                    if (pHead)
                        pHead->pPre = pLink;
                    else
                        pTail = pLink;
                    pLink->pNext = pHead;
                    pHead = pLink;
                    ppLink = &pTail->pNext;// 更新插入用的二重指针
                }
                break;
            case 't':
                {
                    SLink* pLink = arrLinkAdd[nID];
                    RemoveLink(pLink);
                    if (pTail)
                        pTail->pNext = pLink;
                    else
                        pHead = pLink;
                    pLink->pPre = pTail;
                    pTail = pLink;
                    ppLink = &pTail->pNext;// 更新插入用的二重指针
                }
                break;
            case  'd':
                {
                    SLink* pLink = arrLinkAdd[nID];
                    RemoveLink(pLink);
                    if (pTail)
                        ppLink = &pTail->pNext;
                    else
                        ppLink = &pHead;
                }
                break;
            case 's':
                {
                    SLink* pLink = arrLinkAdd[nID];
                    double dbArea = (pLink->pRect->nTop - pLink->pRect->nBottom)*(pLink->pRect->nRight - pLink->pRect->nLeft);
                    SRectangle sRectangle(pLink->pRect->nLeft, pLink->pRect->nRight, pLink->pRect->nTop, pLink->pRect->nBottom);
                    queue<SRectangle> Q;
                    Q.push(sRectangle);
                    pLink = pLink->pNext;
                    while (pLink)
                    {
                        int nSize = Q.size();
                        SRectangle subRect;
                        for (int i = 0; i < nSize; i++)
                        {
                            sRectangle = Q.front();
                            Q.pop();
                            // 上
                            if (pLink->pRect->nTop < sRectangle.nTop)
                            {
                                subRect.nLeft = sRectangle.nLeft; subRect.nRight = sRectangle.nRight;
                                subRect.nTop = sRectangle.nTop; subRect.nBottom = max(pLink->pRect->nTop, sRectangle.nBottom);
                                Q.push(subRect);
                            }
                            // 下
                            if (pLink->pRect->nBottom > sRectangle.nBottom)
                            {
                                subRect.nLeft = sRectangle.nLeft; subRect.nRight = sRectangle.nRight;
                                subRect.nTop = min(sRectangle.nTop, pLink->pRect->nBottom); subRect.nBottom = sRectangle.nBottom;
                                Q.push(subRect);
                            }
                            // 左
                            if (pLink->pRect->nLeft > sRectangle.nLeft)
                            {
                                subRect.nLeft = sRectangle.nLeft;
                                subRect.nRight = min(pLink->pRect->nLeft, sRectangle.nRight);
                                subRect.nTop = min(sRectangle.nTop, pLink->pRect->nTop);
                                subRect.nBottom = max(sRectangle.nBottom, pLink->pRect->nBottom);
                                if (subRect.nTop > subRect.nBottom)
                                    Q.push(subRect);
                            }
                            // 右
                            if (pLink->pRect->nRight < sRectangle.nRight)
                            {
                                subRect.nRight = sRectangle.nRight;
                                subRect.nLeft = max(pLink->pRect->nRight, sRectangle.nLeft);
                                subRect.nTop = min(sRectangle.nTop, pLink->pRect->nTop);
                                subRect.nBottom = max(sRectangle.nBottom, pLink->pRect->nBottom);
                                if (subRect.nTop > subRect.nBottom)
                                    Q.push(subRect);
                            }
                        }
                        pLink = pLink->pNext;
                    }
                    
                    double dbLeft = 0;
                    while (!Q.empty())
                    {
                        sRectangle = Q.front();
                        Q.pop();
                        dbLeft += (sRectangle.nTop - sRectangle.nBottom) * (sRectangle.nRight - sRectangle.nLeft);
                    }
                    printf("%.3lf\n", dbLeft * 100 / dbArea);
                }
                break;
            }
            while (getchar() != '\n');
        }
    }
    
    void process()
    {
    }
    
    int main(){
        FILE *streamIn = freopen("window.in","r",stdin);
        FILE *streamOut = freopen("window.out","w",stdout);
        prepairData();
        process();
        fclose(streamIn);
        fclose(streamOut);
        return 0;
    }

转载于:https://www.cnblogs.com/doublemystery/archive/2013/05/10/3071459.html