http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
Задача: Картинки
На стене наклеено некоторое количество плакатов, фотографий и других картинок прямоугольной формы. Все их стороны либо вертикальны, либо горизонтальны. Каждый прямоугольник может быть частично или полностью перекрыт другими прямоугольниками. Периметром называется общая длина внутренних и внешних фигур, полученных путем наложения прямоугольников.
Напишите программу, вычисляющую значение полученного периметра. На рисунке ниже показан набор из 7 прямоугольников.
Соответствующие границы полученной фигуры показаны на рисунке ниже.
Вершины всех прямоугольников имеют целочисленные координаты.
Входные данные
В первой строке содержится число прямоугольников, наклеенных на стене. В каждой последующей строке приводятся целочисленные координаты нижней левой вершины и правой верхней вершины каждого прямоугольника. Значения этих координат даны как упорядоченные пары, состоящие из x-координаты и следующей за ней y-координаты.
Выходные данные
В единственной строке вывести неотрицательное целое число, которое является периметром для заданных прямоугольников.
Пример входных данных
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
Пример выходных данных
228
Обсуждение идеи решения
Решение на Pascal:
Код:
type
pRect = ^rectangle;
rectangle = record
xmin, ymin, xmax, ymax: integer;
next: pRect
end;
pEdge = ^edge;
edge = record {vertical edges}
kind: (left, right);
finish: boolean;
x, ymin, ymax: integer;
next: pEdge
end;
var
LRy, R: pRect; { LRy = list of rectangles }
LEx: pEdge;
i, N, yminG, ymaxG, intRect, boundRect: integer;
Perimeter: longint;
procedure update (ymin, ymax: integer; var yminG, ymaxG: integer);
begin
if ymin < yminG then yminG := ymin;
if ymax > ymaxG then ymaxG := ymax
end;
procedure insertRect (var Ly, R: pRect);
var
pointer, previous: pRect;
less: boolean;
begin
if Ly = nil then
begin R^.next := nil; Ly := R end
else
begin
less := true;
pointer := Ly;
previous := Ly;
while (pointer <> nil) and less do
begin
if pointer^.ymin >= R^.ymin then less := false
else
begin
previous := pointer;
pointer := pointer^.next
end
end;
if pointer = Ly then Ly := R
else previous^.next := R;
R^.next := pointer
end
end;
procedure selectEdges (y: integer; var LRy: pRect; var LEx: pEdge);
var
LRAux: pRect;
E: pEdge;
greater: boolean;
procedure insertEdge (E: pEdge; var LEx: pEdge);
var
LEAux, previous: pEdge;
less: boolean;
begin {ascending order in x}
if LEx = nil then
begin E^.next := nil; LEx := E end
else
begin
less := true;
LEAux := LEx;
previous := LEx;
while (LEAux <> nil) and less do
if LEAux^.x >= E^.x then less := false
else
begin
previous := LEAux;
LEAux := LEAux^.next
end;
if LEAux = LEx then LEx := E
else previous^.next := E;
E^.next := LEAux
end
end;
begin {selectEdges}
greater := false;
while (LRy <> nil) and (not greater) do
if LRy^.ymin = y then
begin
LRAux := LRy;
new(E);
E^.kind := left;
E^.finish := false;
E^.x := LRy^.xmin;
E^.ymin := LRy^.ymin;
E^.ymax := LRy^.ymax;
insertEdge(E, LEx);
new(E);
E^.kind := right;
E^.finish := false;
E^.x := LRy^.xmax;
E^.ymin := LRy^.ymin;
E^.ymax := LRy^.ymax;
insertEdge(E, LEx);
LRy := LRy^.next;
dispose(LRAux)
end
else greater := true
end;
procedure deleteEdges (y: integer; var LEx: pEdge);
var
aux, prev: pEdge;
found: boolean;
begin {delete edges with ymax=y-1; mark edges with ymax=y}
aux := LEx; {LEx<>nil }
repeat
found := aux^.ymax = y - 1;
if found then
begin aux := aux^.next; dispose(LEx); LEx := aux end
until (aux = nil) or (not found);
prev := aux;
while aux <> nil do
if aux^.ymax = y - 1 then
if prev <> aux then
begin
prev^.next := aux^.next;
dispose(aux);
aux := prev^.next
end
else
begin
LEx := aux^.next;
prev := LEx;
dispose(aux);
aux := LEx
end
else
begin
aux^.finish := aux^.ymax = y;
prev := aux;
aux := aux^.next
end
end;
procedure scanEdges (y: integer; Lx: pEdge);
var
intRect, oldIntRect, totalRect, oldTotalRect,
lowBRect, oldLowBRect, subtR, oldSubtR: integer;
prev: pEdge;
first: boolean;
begin
intRect := 0;
oldIntRect := 0;
totalRect := 0;
oldTotalRect := 0;
lowBRect := 0;
oldLowBRect := 0;
subtR := 0;
oldSubtR := 0;
prev := Lx;
first := true;
repeat
if Lx^.finish then
if Lx^.kind = left then subtR := subtR + 1
else subtR := subtR - 1
else
begin
if Lx^.kind = left then
begin
totalRect := totalRect + 1;
if Lx^.ymax > y + 1 then intRect := intRect + 1;
if Lx^.ymin = y then lowBRect := lowBRect + 1
end
else {right edge}
begin
totalRect := totalRect - 1;
if Lx^.ymax > y + 1 then intRect := intRect - 1;
if Lx^.ymin = y then lowBRect := lowBRect - 1
end;
if (totalRect = 0) and (oldTotalRect = 1) then
Perimeter := Perimeter + 1
else if (totalRect = 1) and (oldTotalRect = 0) then
if not first and (prev^.x = Lx^.x) and not prev^.finish then
Perimeter := Perimeter - 1
else
Perimeter := Perimeter + 1;
if (oldIntRect = 0) and (oldTotalRect > 0) then
Perimeter := Perimeter + Lx^.x - prev^.x;
if (oldLowBRect > 0) and (oldTotalRect = oldLowBRect) then
begin
Perimeter := Perimeter + Lx^.x - prev^.x;
if oldSubtR > 0 then
Perimeter := Perimeter - 2 * (Lx^.x - prev^.x)
end
end;
oldIntRect := intRect;
oldTotalRect := totalRect;
oldLowBRect := lowBRect;
oldSubtR := subtR;
first := false;
prev := Lx;
Lx := Lx^.next
until Lx = nil
end;
begin { MAIN }
Perimeter := 0;
readln(N);
new(R);
with R^ do
begin
readln(xmin, ymin, xmax, ymax);
yminG := ymin;
ymaxG := ymax
end;
LRy := nil;
insertRect(LRy, R);
for i := 2 to N do
begin
new(R);
with R^ do
begin
readln(xmin, ymin, xmax, ymax);
update(ymin, ymax, yminG, ymaxG)
end;
insertRect(LRy, R)
end;
LEx := nil;
for i := yminG to ymaxG do
begin
selectEdges(i, LRy, LEx);
if LEx <> nil then
begin
deleteEdges(i, LEx);
if LEx <> nil then scanEdges(i, LEx);
end
end;
writeln(Perimeter);
end.Решение на С++:
Код:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 1000000
const __int64 mininf=1000000;
const __int64 maxinf=-1000000;
struct Line
{
__int64 count,len;
__int64 l,r;
int lbc,rbc;
__int64 nseg;
};
struct node
{
__int64 x,down,up;
bool flag;
node(__int64 tx,__int64 td,__int64 tu,bool tf):x(tx),down(td),up(tu),flag(tf)
{
}
};
__int64 miny,maxy;
vector< node > vec;
Line Ltree[MAXN];
bool operator< (const node& a,const node& b)
{
return a.x<b.x;
}
void build(__int64 l,__int64 r,int step)
{
Ltree[step].count=0;Ltree[step].len=0;
Ltree[step].lbc=false;Ltree[step].rbc=false;
Ltree[step].nseg=0;
Ltree[step].r=r;Ltree[step].l=l;
if(r-l>1)
{
build(l,(l+r)/2,2*step);
build((l+r)/2,r,2*step+1);
}
}
void update(int step)
{
if(Ltree[step].count>0)
{
Ltree[step].len=Ltree[step].r-Ltree[step].l;
Ltree[step].nseg=1;
}
else
if(Ltree[step].r-Ltree[step].l>1)
{
Ltree[step].len=Ltree[2*step].len+Ltree[2*step+1].len;
Ltree[step].nseg=Ltree[2*step].nseg+Ltree[2*step+1].nseg;
if(Ltree[step].nseg&&Ltree[2*step].rbc&&Ltree[2*step+1].lbc)
Ltree[step].nseg--;
}
else
{
Ltree[step].len=0;
Ltree[step].nseg=0;
}
}
void insert(__int64 l,__int64 r,int step)
{
if(Ltree[step].l==l) Ltree[step].lbc++;
if(Ltree[step].r==r) Ltree[step].rbc++;
if(l==Ltree[step].l&&Ltree[step].r==r)
Ltree[step].count++;
else
{
__int64 mid=(Ltree[step].l+Ltree[step].r)/2;
if(r<=mid)
insert(l,r,2*step);
else
if(l>=mid)
insert(l,r,2*step+1);
else
{
insert(l,mid,2*step);
insert(mid,r,2*step+1);
}
}
update(step);
}
void del(__int64 l,__int64 r,int step)
{
if(Ltree[step].l==l) Ltree[step].lbc--;
if(Ltree[step].r==r) Ltree[step].rbc--;
if(l==Ltree[step].l&&Ltree[step].r==r)
Ltree[step].count--;
else
{
__int64 mid=(Ltree[step].l+Ltree[step].r)/2;
if(r<=mid)
del(l,r,2*step);
else
if(l>=mid)
del(l,r,2*step+1);
else
{
del(l,mid,2*step);
del(mid,r,2*step+1);
}
}
update(step);
}
int main()
{
int n;
__int64 x1,x2,y1,y2;
while(scanf("%d",&n)==1)
{
miny=mininf;
maxy=maxinf;
for(int i=0;i<n;i++)
{
scanf("%I64d%I64d%I64d%I64d",&x1,&y1,&x2,&y2);
vec.push_back(node(x1,y1,y2,true));
vec.push_back(node(x2,y1,y2,false));
miny=min(miny,y1);
maxy=max(maxy,y2);
}
sort(vec.begin(),vec.end());
build(miny,maxy,1);
__int64 peri=0;
int m=vec.size();
__int64 lastlen=0,lastseg=0;
for(int i=0;i<m;i++)
{
if(vec[i].flag)
insert(vec[i].down,vec[i].up,1);
else
del(vec[i].down,vec[i].up,1);
peri+=abs(Ltree[1].len-lastlen);
lastlen=Ltree[1].len;
if(i)
peri+=2*(vec[i].x-vec[i-1].x)*lastseg;
lastseg=Ltree[1].nseg;
}
printf("%I64d\n",peri);
}
return 0;
}