[USACO 5.3 Window Area]矩形切割

【题目翻译】http://www.wzoi.org/usaco/15%5C305.asp

【算法分析】

矩形切割，直接模拟就可以。

【其它】囧，以前居然卡在这题水题上。1A

USER: wei jie chen [jie22221]TASK: windowLANG: C++Compiling…Compile: OKExecuting… Test 1: TEST OK [0.000 secs, 2804 KB] Test 2: TEST OK [0.000 secs, 2804 KB] Test 3: TEST OK [0.000 secs, 2804 KB] Test 4: TEST OK [0.011 secs, 2804 KB] Test 5: TEST OK [0.011 secs, 2804 KB] Test 6: TEST OK [0.011 secs, 2804 KB] Test 7: TEST OK [0.022 secs, 2804 KB] Test 8: TEST OK [0.022 secs, 2804 KB] Test 9: TEST OK [0.000 secs, 2804 KB] Test 10: TEST OK [0.000 secs, 2804 KB] Test 11: TEST OK [0.022 secs, 2804 KB]All tests OK.

YOUR PROGRAM (‘window’) WORKED FIRST TIME! That’s fantastic– and a rare thing. Please accept these special automatedcongratulations.

【CODE】

/*
ID:jie22221
TASK:window
LANG:C++
*/
#include #include #include #include #include using namespace std;
const int N=100;
struct zfx{int x1,y1,x2,y2;char mark;}d[N];
int n;
double ans;inline int area(int x1,int y1,int x2,int y2){
    return (x2-x1)*(y2-y1);
}    void cut(int i,int x1,int y1,int x2,int y2){
    if (x1>=x2 || y1>=y2) return;
    if (i>n){
        ans+=area(x1,y1,x2,y2);
        return;
    }   
    if (x1    if (x2>d[i].x2) cut(i+1,max(x1,d[i].x2),y1,x2,y2);
    if (y1    if (y2>d[i].y2) cut(i+1,max(x1,d[i].x1),max(d[i].y2,y1),min(x2,d[i].x2),y2);
}   int main(){
    freopen("window.in","r",stdin);
    freopen("window.out","w",stdout);
    char op;
    int pos;
    zfx tmp;
    for (;;){
        op=’ ‘;
        while (scanf("%c",&op)!=EOF && (op==’ ‘ || op==’n’));
        if (op==’ ‘ || op==’n’) break;
        switch (op){
            case ‘w’:
                n++;
                scanf("(%c,%d,%d,%d,%d)",&d[n].mark,&d[n].x1,&d[n].y1,&d[n].x2,&d[n].y2);
                if (d[n].x1>d[n].x2) swap(d[n].x1,d[n].x2);
                if (d[n].y1>d[n].y2) swap(d[n].y1,d[n].y2);
                break;
            case ‘t’:
                scanf("(%c)",&op);
                zfx tmp;
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                tmp=d[pos];
                for (int i=pos;i                d[n]=tmp;
                break;
            case ‘b’:
                scanf("(%c)",&op);
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                tmp=d[pos];
                for (int i=pos;i>1;i–) d[i]=d[i-1];
                d[1]=tmp;
                break;
            case ‘d’:
                scanf("(%c)",&op);
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                for (int i=pos;i                n–;
                break;
            case ‘s’:
                scanf("(%c)",&op);
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                ans=0;
                cut(pos+1,d[pos].x1,d[pos].y1,d[pos].x2,d[pos].y2);
                double S=area(d[pos].x1,d[pos].y1,d[pos].x2,d[pos].y2);
                printf("%.3lfn",ans/S*100);
                break;
        }   
    }   
}