程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ural1147(Shaping Regions)矩形切割

ural1147(Shaping Regions)矩形切割

編輯：C++入門知識

題意：一個10000*10000的矩陣，初始顏色都為1，然後最多2500次塗色，每次塗色將一個矩形的面積塗成某個特定顏色，問塗完之後每種顏色最終的面積。

解法：倒序計算，矩形切割

代碼：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, /STACK:102400000,102400000)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
//freopen (in.txt , r , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=2510;
const int INF=1e9+7;

struct rec
{
    int x1,x2,y1,y2;
    int color;
} recs[Max];
int A,B;
int n;
int  getans(int x1,int x2,int y1,int y2,int p)
{
    while((p<=n)&&(x1>=recs[p].x2||x2<=recs[p].x1||y1>=recs[p].y2||y2<=recs[p].y1))
        p++;
    if(p>n)
        return (x2-x1)*(y2-y1);
    int ans=0;
    if(x1recs[p].x2)
        ans+=getans(recs[p].x2,x2,y1,y2,p+1),x2=recs[p].x2;
    if(y2>recs[p].y2)
        ans+=getans(x1,x2,recs[p].y2,y2,p+1),y2=recs[p].y2;
    if(y1=1; i--)
        {
            int tool=getans(recs[i].x1,recs[i].x2,recs[i].y1,recs[i].y2,i+1);
            ans[recs[i].color]+=tool;
            ans[1]-=tool;
        }
        for(int i=1; i<=2500; i++)
            if(ans[i])
                printf(%d %d
,i,ans[i]);
    }
    return 0;
}
/*
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
*/