9
20
2013
1

【BZOJ1007】【HNOI2008】水平可见直线【计算几何+栈】

我的第一道计算几何,OLE了好多次。先以A为第一关键字,B为第二关键字SORT一下。从小到大进栈,然后每次比较头三条直线L1,L2,L3如果L1L2交点不在L2L3交点之后则删除L2,再比较删除L2以后的头三条直线直到不满足条件或者无法再删除则停止。最后留在栈中的直线就是可以看见的直线。接下来是我惨烈无比的AC历程

program p1007;
	type
		line=record
			k,b:extended;
			num:longint;
		end;
	var
		x,s:array[0..50100] of line;
		pd:array[0..50100] of boolean;
		i,j,n,head:longint;
		k1,k2:extended;
	procedure sort(first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[i];
			while i<j do begin
				while (i<j) and ((x[j].k>x[0].k) or ((x[j].k=x[0].k) and (x[j].b<x[0].b))) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and ((x[i].k<x[0].k) or ((x[i].k=x[0].k) and (x[i].b>x[0].b))) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(first,i-1);
			if i<en-1 then sort(i+1,en);
		end;
	function find(k1,k2:line):extended;
		begin
			exit((k2.b-k1.b)/(k1.k-k2.k));
		end;
	begin
		readln(n);
		for i:=1 to n do begin
			readln(x[i].k,x[i].b);
			x[i].num:=i;
		end;
		sort(1,n);
		head:=0; 
		fillchar(pd,sizeof(pd),true);
		for i:=1 to n do begin
			if head=0 then begin
				inc(head); s[head]:=x[i]; continue;
			end;
			if (x[i].k=s[head].k)  then begin
				pd[x[i].num]:=false; continue;
			end;
			if head=1 then begin
				inc(head); s[head]:=x[i]; continue;
			end;
			while true do begin
				if head=1 then begin
					inc(head); s[head]:=x[i]; break;
				end;
				k1:=find(x[i],s[head]); k2:=find(s[head-1],s[head]);
				if k1<=k2 then begin
					pd[s[head].num]:=false; dec(head);
				end else begin
					inc(head); s[head]:=x[i]; break;
				end;
			end;
		end;
		for i:=1 to n do
			if pd[i]=true then write(i,' ');
	end.
Category: 计算几何 | Tags: | Read Count: 1732
Avatar_small
alfalfa 说:
2015年5月14日 17:08

吉利好帅


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com