Beyond the Void
BYVoid
USACO 5.5.1 Picture 矩形周長 picture
本文正體字版由OpenCC轉換

把所有矩形離散化,每個矩形都由四條邊組成,分爲縱邊和橫邊。對縱邊和橫邊分別掃描一次,以橫邊爲例:

<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

相關日誌