POI 1998 窗户 Window
This post is written in Chinese. Please consider using Google Translate
求连通块，由于数据范围过大，需要离散化，把10000压缩成2500。然后在指定区域内求出连通块的个数，BFS会有一点超时，需要用并查集优化。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct point
{
int x,y;
};
struct cell
{
int bel;
bool p[4];
};
class tList
{
public:
tList *next;
point v;
tList(point tv) : v(tv)
{
next=0;
}
};
class tQueue
{
public:
tList *first,*last;
int size;
tQueue()
{
reset();
}
void reset()
{
first=last=0;
size=0;
}
void ins(point v)
{
if (first)
last=last->next=new tList(v);
else
first=last=new tList(v);
size++;
}
point pop()
{
point rtn=first->v;
tList *t=first;
size--;
first=first->next;
delete t;
return rtn;
}
};
const int MAXN=5005;
const int MAX=2601;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
point w1,w2;
point P[MAXN];
point *pP[MAXN];
cell G[MAX][MAX];
int M,M_X,M_Y,C,R,minx,miny,maxx,maxy,Ans;
bool Red;
tQueue Q;
void init()
{
int i,t;
freopen("okn.in","r",stdin);
freopen("okn.out","w",stdout);
scanf("%d%d%d%d",&w1.x,&w1.y,&w2.x,&w2.y);
t=w1.y;w1.y=w2.y;w2.y=t;
scanf("%d",&M);
for (i=1;i<=M;i++)
{
scanf("%d%d",&P[i].x,&P[i].y);
pP[i]=&P[i];
}
pP[M+1]=&w1;
pP[M+2]=&w2;
}
int cmp1 (const void *a,const void *b)
{
return (*(point **)a)->x -(*(point **)b)->x;
}
int cmp2 (const void *a,const void *b)
{
return (*(point **)a)->y -(*(point **)b)->y;
}
void disper()
{
int i,last=-1,k=-1;
qsort(pP+1,M+2,sizeof(pP[0]),cmp1);
for (i=1;i<=M+2;i++)
{
if (pP[i]->x > last)
{
last=pP[i]->x;
M_X=++k;
}
pP[i]->x=k;
}
last=-1,k=-1;
qsort(pP+1,M+2,sizeof(pP[0]),cmp2);
for (i=1;i<=M+2;i++)
{
if (pP[i]->y > last)
{
last=pP[i]->y;
M_Y=++k;
}
pP[i]->y=k;
}
}
void draw(point a,point b)
{
int i,j;
if (a.y==b.y)
{
j=a.y+1;
if (b.x>a.x)
{
for (i=a.x+1;i<=b.x;i++)
{
if (j<=M_Y)
G[i][j].p[2]=true;
if (j-1>=1)
G[i][j-1].p[3]=true;
}
}
else
{
for (i=b.x+1;i<=a.x;i++)
{
if (j<=M_Y)
G[i][j].p[2]=true;
if (j-1>=1)
G[i][j-1].p[3]=true;
}
}
}
else
{
i=a.x+1;
if (b.y>a.y)
{
for (j=a.y+1;j<=b.y;j++)
{
if (i<=M_X)
G[i][j].p[0]=true;
if (i-1>=1)
G[i-1][j].p[1]=true;
}
}
else
{
for (j=b.y+1;j<=a.y;j++)
{
if (i<=M_X)
G[i][j].p[0]=true;
if (i-1>=1)
G[i-1][j].p[1]=true;
}
}
}
}
void graph()
{
int i;
for (i=2;i<=M;i++)
{
draw(P[i-1],P[i]);
}
draw(P[M],P[1]);
}
inline bool inrange(int x,int y)
{
return x>=1 && x<=M_X && y>=1 && y<=M_Y;
}
inline bool inwindow(int x,int y)
{
return x>=minx && x<=maxx && y>=miny && y<=maxy;
}
void fill(int tx,int ty)
{
point i,j;
int k;
Q.reset();
i.x=tx;i.y=ty;
Q.ins(i);
while (Q.size)
{
i=Q.pop();
G[i.x][i.y].bel=C;
for (k=0;k<4;k++)
{
if (G[i.x][i.y].p[k]==false)
{
j.x=i.x+dx[k];
j.y=i.y+dy[k];
if (inrange(j.x,j.y))
{
if (G[j.x][j.y].bel==0)
{
G[j.x][j.y].bel=C;
Q.ins(j);
}
}
else
{
Red=false;
}
}
}
}
}
void getred()
{
int i,j;
C=0;
for (i=1;i<=M_X;i++)
{
for (j=1;j<=M_Y;j++)
{
if (G[i][j].bel==0)
{
C++;
Red=true;
fill(i,j);
if (Red)
{
R=C;
return;
}
}
}
}
}
void fill2(int tx,int ty)
{
point i,j;
int k;
Q.reset();
i.x=tx;i.y=ty;
Q.ins(i);
while (Q.size)
{
i=Q.pop();
G[i.x][i.y].bel=0;
for (k=0;k<4;k++)
{
if (G[i.x][i.y].p[k]==false)
{
j.x=i.x+dx[k];
j.y=i.y+dy[k];
if (inwindow(j.x,j.y))
{
if (G[j.x][j.y].bel==R)
{
G[j.x][j.y].bel=0;
Q.ins(j);
}
}
}
}
}
}
void solve()
{
int i,j;
Ans=0;
minx=w1.x+1; maxx=w2.x;
miny=w1.y+1; maxy=w2.y;
for (i=minx;i<=maxx;i++)
{
for (j=miny;j<=maxy;j++)
{
if (G[i][j].bel==R)
{
Ans++;
fill2(i,j);
}
}
}
}
int main()
{
init();
disper();
graph();
getred();
solve();
printf("%d",Ans);
return 0;
}
<h2><span class="mw-headline">窗户 </span></h2>
我们在笛卡尔坐标系中有一个多边形，多边形的边平行于坐标轴，每两条相邻的边是垂直正交的并且每一个顶点的坐标都是整数。我们还给出一个边也平行于坐标轴的矩形窗户。多边形的内部被涂成红色，那么有几个分开的红色部分将在窗户中被看到。
例子：
如下图：
<a class="image" title="Image:Okn.png" href="http://www.ruvtex.cn/wiki/Image:Okn.png"><img src="http://www.ruvtex.cn/mw/images/7/71/Okn.png" alt="Image:Okn.png" width="273" height="300" /></a>
有两个红色的部分将被通过窗子看到。
任务：
写一个程序
- 从文件中读入窗户与多边形的描述。
- 计算能通过窗户看到的分开的红色部分的个数。
将结果写入文件。
输入：
在文件的第一行有四个整数x1,y1,x2,y2 (0<=x1,y1,x2,y2<=10000),有一个空格隔开，（x1,y1）是窗户左上角的坐标，（x2,y2）是窗户右下角的坐标。 下一行有一个整数n（4<=n<=5000）表示多边形的顶点数。以下n行以逆时针的顺序给出了多边形的顶点坐标，也就是说当我们沿着给出的 多边形的边走时，多边形的内部在外部的左边。每一行包括两个整数x y(0<=x,y<=10000),有一个空格隔开，第(i+2)行表示多边形的第i个顶点。
输出：
在文件的第一行有且仅有一个整数表示能够通过窗户看到的分开的红色区域的个数。
输入样例：
0 5 8 1 24 0 0 4 0 4 2 5 2 5 0 7 0 7 3 3 3 3 2 2 2 2 4 1 4 1 5 2 5 2 6 3 6 3 5 4 5 4 6 5 6 5 4 7 4 7 7 0 7
输出样例：2