jiry_2's Blog

我的第一道计算几何，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.