Home > Old Blog Posts > USACO 3.1.4 Shaping Regions

USACO 3.1.4 Shaping Regions


首先我要对这道题的数据使用一次嘲弄……裸的O(nab)的算法居然能过10个点

这道题正确做法大致有两种

1、线段树 但这里若用二维线段树,空间上很容易爆掉,所以我们可以把其中一维离散化,再用一维线段树处理另一维(时间换空间……)

2、矩形切割,这是我从网上了解到的一种比较强大的方法

e79fa9e5bda2e58887e589b2

大致思想由这张图已经可以了解的比较清楚了,实现的时候有很多技巧(^-^),这道题的方法到了后面第五章的时候还会用到(Window Area)。

代码:

/* ID: dementr1 PROG: rect1 LANG: C++ */ #include <fstream> using namespace std; ofstream fout ("rect1.out"); ifstream fin ("rect1.in"); int a, b, n; int llx[1001], lly[1001], urx[1001], ury[1001], color[1001]; int cut(int lx, int ly, int rx, int ry, int b) { if (lx==rx||ly==ry) return 0; if (b>n) return (rx-lx)*(ry-ly); if (lx>=urx[b]||ly>=ury[b]||rx<=llx[b]||ry<=lly[b]) return cut(lx,ly,rx,ry,b+1); int x[4], y[4]; x[0]=lx; y[0]=ly; x[3]=rx; y[3]=ry; x[1]=max(lx,llx[b]); y[1]=max(ly,lly[b]); x[2]=min(rx,urx[b]); y[2]=min(ry,ury[b]); int res=0; for (int i=0; i<3; i++) for (int j=0; j<3; j++) if (i!=1||j!=1) res+=cut(x[i], y[j], x[i+1], y[j+1], b+1); return res; } int main() { fin >> a >> b >> n; llx[0]=0; lly[0]=0; urx[0]=a; ury[0]=b; color[0]=1; for (int i=1; i<=n; ++i) fin >> llx[i] >> lly[i] >> urx[i] >> ury[i] >> color[i]; int count[2501]; memset(count, 0, sizeof(count)); for (int id=n; id>=0; id--) count[color[id]]+=cut(llx[id],lly[id],urx[id],ury[id],id+1); for (int i=1; i<=2500; i++) if (count[i]>0) fout << i << " " << count[i] << endl; return 0; }
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: