杂项

SGU:http://www.cnblogs.com/Accoral/p/3234236.html
矩阵分割
日常参考:http://blog.csdn.net/u012746396/article/details/41280403
HDU1542
O(n^3)求矩阵面积并

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector> 
using namespace std;
double x1[123],y1[123],x2[123],y2[123];
vector<double> x,y;
int main(){
    int n,kase=0; 
    while(scanf("%d",&n)==1){
        x.clear(); y.clear();
        if(n==0)
            break;
        for(int i = 0; i < n; i++){
            scanf("%lf %lf %lf %lf",&x1[i],&y1[i],&x2[i],&y2[i]);
            x.push_back(x1[i]); x.push_back(x2[i]);
            y.push_back(y1[i]); y.push_back(y2[i]);
        }
        sort(x.begin(),x.end()); sort(y.begin(),y.end());
        double s = 0;
        for(int i = 0; i < 2*n-1; i++){ //NOTE: 注意离散方块是2n 
            for(int j = 0 ; j < 2*n-1; j++){
                double sz = (x[i+1]-x[i])*(y[j+1]-y[j]);
                for(int k = 0; k < n; k++){
                    if(x[i] >= x1[k] && y[j] >= y1[k] && x[i+1] <= x2[k] && y[j+1] <= y2[k]){
                        s+=sz;
                        //cout << s << endl;
                        break;
                    }
                }
            }
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",++kase,s);
    }
    return 0;
}

SGU177
涂色问题加强版
一维变二维,涂色只有黑白
冰块上浮法/漂浮法

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 5e3+11;
int x1[maxn],y1[maxn],x2[maxn],y2[maxn],color[maxn];
int area[5],n,m,now;
char str[10];
int solve(int xx1,int xx2,int yy1,int yy2,int z){
    while(z<=m&&(xx1>=x2[z]||xx2<=x1[z]||yy1>=y2[z]||yy2<=y1[z])) z++;//开区间可以取等 
    if(z>m) return (xx2-xx1)*(yy2-yy1);
    int ans=0;
    if(xx1<x1[z]) ans+=solve(xx1,x1[z],yy1,yy2,z+1),xx1=x1[z];
    if(xx2>x2[z]) ans+=solve(x2[z],xx2,yy1,yy2,z+1),xx2=x2[z];
    if(yy1<y1[z]) ans+=solve(xx1,xx2,yy1,y1[z],z+1);
    if(yy2>y2[z]) ans+=solve(xx1,xx2,y2[z],yy2,z+1);
    return ans;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        area[0]=area[1]=0;
        x1[0]=y1[0]=1;y1[0]=y2[0]=n;color[0]=0;
        for(int i = 1; i <= m; i++){
            scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
            scanf("%s",str);
            if(str[0]=='b') color[i]=1;
            else color[i]=0;
            if(x1[i]>x2[i]) swap(x1[i],x2[i]);
            if(y1[i]>y2[i]) swap(y1[i],y2[i]);
            x2[i]++;y2[i]++;//元线段处理 
        }
        for(int i = m; i >= 0; i--){
            now=color[i];
            if(now) area[now]+=solve(x1[i],x2[i],y1[i],y2[i],i+1);//要比较的冰层
        }
        printf("%d\n",n*n-area[1]);
    }
    return 0;
}

URAL1147

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+11;
int x1[maxn],y1[maxn],x2[maxn],y2[maxn];
int color[2505],area[2505];
int now,n,m,c;
void solve(int xx1,int xx2,int yy1,int yy2,int z){
    while(z<=c&&(xx1>=x2[z]||xx2<=x1[z]||yy1>=y2[z]||yy2<=y1[z]))z++;
    if(z>c){
        area[now]+=(xx2-xx1)*(yy2-yy1);
        return;
    }
    if(xx1<x1[z]){
        solve(xx1,x1[z],yy1,yy2,z+1);
        xx1=x1[z];
    }
    if(xx2>x2[z]){
        solve(x2[z],xx2,yy1,yy2,z+1);
        xx2=x2[z];
    }
    if(yy1<y1[z]) solve(xx1,xx2,yy1,y1[z],z+1);
    if(yy2>y2[z]) solve(xx1,xx2,y2[z],yy2,z+1);
}
int main(){
    while(scanf("%d%d%d",&n,&m,&c)!=EOF){
        memset(area,0,sizeof area);
        x1[0]=y1[0]=0;x2[0]=n;y2[0]=m;color[0]=1;
        for(int i = 1; i <= c; i++) scanf("%d%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i],&color[i]);
        for(int i = c; i >= 0; i--){
            now=color[i];
            solve(x1[i],x2[i],y1[i],y2[i],i+1);
        }
        for(int i = 1; i <= 2501; i++){
            if(area[i]) printf("%d %d\n",i,area[i]);
        }
    }
    return 0;
}

标签: 算法, 学习

添加新评论