Beyond the Void
BYVoid
USACO 5.5.1 Picture 矩形周长 picture

把所有矩形离散化,每个矩形都由四条边组成,分为纵边和横边。对纵边和横边分别扫描一次,以横边为例:

<li>每个矩形的两条横边中,称下面的为始边,上面的为终边。</li>
<li>把每条横边以纵坐标从小到大排序,<strong>如果纵坐标相同,则应把始边排到终边之前</strong>。</li>
<li>依次枚举每条横边</li>
<li>如果当前边为始边,则把这条边的横向的所有点j的<strong>层数</strong>增加1,即为level[j]++。如果层数由0变为了1,则这一点一定是边缘点,总周长ans++。</li>
<li>如果当前边为终边,则把这条边的横向的所有点j的<strong>层数</strong>减少1,即为level[j]--。如果层数由1变为了0,则这一点一定是边缘点,总周长ans++。</li>

同理按此方法扫描纵边,即可得到最后结果。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 3152 KB]
   Test 2: TEST OK [0.000 secs, 3156 KB]
   Test 3: TEST OK [0.011 secs, 3156 KB]
   Test 4: TEST OK [0.000 secs, 3152 KB]
   Test 5: TEST OK [0.022 secs, 3156 KB]
   Test 6: TEST OK [0.011 secs, 3152 KB]
   Test 7: TEST OK [0.032 secs, 3320 KB]
   Test 8: TEST OK [0.011 secs, 3156 KB]
   Test 9: TEST OK [0.032 secs, 3324 KB]
   Test 10: TEST OK [0.011 secs, 3156 KB]
   Test 11: TEST OK [0.205 secs, 3160 KB]

All tests OK.

Your program ('picture') produced all correct answers! This is your submission #2 for this problem. Congratulations! 
/*
ID: cmykrgb1
PROG: picture
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAX 10001

using namespace std;

typedef struct 
{
	int s,t,p;
	bool start;
}Line;

ifstream fi("picture.in");
ofstream fo("picture.out");

int N,ans=0;
int *level;
Line Lx[MAX],Ly[MAX];

inline int cmp(const void *a,const void *b)
{
	if (((Line*)a)->p==((Line*)b)->p)
	{
		if (((Line*)a)->start)
			return -1;
		else
			return 1;
	}
	return ((Line *)a)->p < ((Line *)b)->p ? -1 : 1;
}

void init()
{
	int i,x1,x2,y1,y2;
	fi >> N;
	for (i=1;i<=N;i++)
	{
		fi >> x1 >> y2 >> x2 >> y1;
		Lx[i*2-1].p=y1;
		Lx[i*2-1].s=x1;
		Lx[i*2-1].t=x2;
		Lx[i*2-1].start=false;
		Lx[i*2].p=y2;
		Lx[i*2].s=x1;
		Lx[i*2].t=x2;
		Lx[i*2].start=true;
		Ly[i*2-1].p=x1;
		Ly[i*2-1].s=y2;
		Ly[i*2-1].t=y1;
		Ly[i*2-1].start=true;
		Ly[i*2].p=x2;
		Ly[i*2].s=y2;
		Ly[i*2].t=y1;
		Ly[i*2].start=false;
	}
	N*=2;
	qsort(Lx+1,N,sizeof(Lx[0]),cmp);
	qsort(Ly+1,N,sizeof(Ly[0]),cmp);
	level=(int *)malloc(sizeof(int)*20002);
	level+=10000;
}

void Scan(Line *L)
{
	int i,j;
	for (i=-10000;i<=10000;i++)
		level[i]=0;
	for (i=1;i<=N;i++)
	{
		if (L[i].start)
		{
			for (j=L[i].s;j<L[i].t;j++)
			{
				level[j]++;
				if (level[j]==1)
					ans++;
			}
		}
		else
		{
			for (j=L[i].s;j<L[i].t;j++)
			{
				level[j]--;
				if (level[j]==0)
					ans++;
			}
		}
	}
}

void print()
{
	fo << ans << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	Scan(Lx);
	Scan(Ly);
	print();
	return 0;
}

上次修改时间 2017-02-03

相关日志