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