POI 1998 窗戶 Window
求連通塊，由於數據範圍過大，需要離散化，把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