atlantis.cpp

一道经典的矩形切割的题目的解答

#include <iostream>  
#include <iomanip> 
 
using namespace std;  

const int MAXN = 101;  

struct square
{  
    double x1, y1, x2, y2;  
    int operator=(const square& b)
    {  
        x1 = b.x1; 
        x2 = b.x2;
        y1 = b.y1; 
        y2 = b.y2;  
        return 1;  
    }  
}data[MAXN], s[MAXN * MAXN];  

int t = 1;  
  
inline double getresult()
{  
    double r=0;  
    for (int i=0;i!= t;++i)
    {  
        r+=(s[i].x2-s[i].x1)*(s[i].y2-s[i].y1);  
    }  
    return r;  
}  

inline void del(int x)
{  
    s[x] = s[--t];  
}  

inline void add(double x1, double y1, double x2, double y2)
{  
    s[t].x1 = x1; 
    s[t].x2 = x2; 
    s[t].y1 = y1; 
    s[t].y2 = y2;  
    ++t;  
} 
 
inline double max(double a, double b)
{  
    return (a > b ? a : b);  
}  


inline double min(double a, double b)
{  
    return (a < b ? a : b);  
}  

inline int cross(double x1, double x2, double y1, double y2)
{  
    if (x1>= y2||y1>=x2) return 0; 
    else return 1;  
}  

void cut(int x, double x1, double y1, double x2, double y2, int dir)
{  
    if (dir == 1){  
        int k1 = max(data[x].x1, x1);  
        int k2 = min(data[x].x2, x2);  
        if (x1 < k1) add(x1, y1, k1, y2);  
        if (x2 > k2) add(k2, y1, x2, y2);  
        cut(x, k1, y1, k2, y2, dir + 1);  
    }  
    if (dir == 2){  
        int k1 = max(data[x].y1, y1);  
        int k2 = min(data[x].y2, y2);  
        if (y1 < k1) add(x1, y1, x2, k1);  
        if (y2 > k2) add(x1, k2, x2, y2);  
    }  
}  

int main()
{  
    int n, cases = 0;  
    while (cin >> n && n != 0)
    {  
        memset(s, 0, sizeof(s));  
        memset(data, 0, sizeof(data));  
        for(int i=0;i!=n; ++i) 
            cin>>data[i].x1>>data[i].y1>>data[i].x2>>data[i].y2;  
        
        t = 1;  
        s[0] = data[0];
          
        for (int i=1;i!=n;++i)
        {  
            for (int j=0; j!=t;++j)
            {  
                if (cross(data[i].x1,data[i].x2,s[j].x1,s[j].x2)&&cross(data[i].y1,data[i].y2,s[j].y1,s[j].y2))
                {  
                    cut(i,s[j].x1,s[j].y1,s[j].x2,s[j].y2,1);  
                    del(j); 
                    --j;  
                }  
            }  
            add(data[i].x1, data[i].y1, data[i].x2, data[i].y2);  
        }  
        double r=getresult();  
        cout <<"Test case #" <<++cases<<endl  
            <<"Total explored area: "<<setiosflags(ios::fixed)<<setprecision(2)<<r<<endl<< endl;  
    }  
    return 0;  
}