比赛 20140418 评测结果 WEEEEEEEEW
题目名称 奶牛冰壶运动 最终得分 0
用户昵称 zgyzhaoguangyang 运行时间 0.230 s
代码语言 Pascal 内存使用 1.81 MiB
提交时间 2014-04-18 11:29:55
显示代码纯文本
var
  a,b,c,d,q:array[0..50005] of longint;
  f,f1:array[-40005..40005] of longint;
  vv:array[-40005..40005] of boolean;
  ans1,ans2,n:longint;
procedure init;
var i,j:longint;
begin
 readln(n);
 for i:=1 to n do
 readln(a[i],b[i]);
 for i:=1 to n do
 readln(c[i],d[i]);
end;

procedure qsort(ll,rr:longint);
var i,j,x,y,t:longint;
begin
  i:=ll;j:=rr;x:=a[(ll+rr)>>1];y:=b[(ll+rr)>>1];
  repeat
    while (b[i]<y) or ((b[i]=y)and(a[i]<x)) do inc(i);
    while (b[j]>y) or ((b[j]=y)and(a[j]>x)) do dec(j);
    if i<=j then
    begin
      t:=a[i];a[i]:=a[j];a[j]:=t;
      t:=b[i];b[i]:=b[j];b[j]:=t;
      inc(i);dec(j);
    end;
  until i>j;
  if i<rr then qsort(i,rr);
  if ll<j then qsort(ll,j);
end;

procedure  sort(ll,rr:longint);
var i,j,x,y,t:longint;
begin
     i:=ll;j:=rr;x:=c[(ll+rr)>>1];y:=d[(ll+rr)>>1];
	  repeat
	   while (d[i]<y) or ((d[i]=y)and (c[i]<x)) do inc(i);
	   while (d[j]>y) or ((d[j]=y)and (c[j]<x)) do dec(j);
	   if i<=j then
	      begin
		     t:=c[i];c[i]:=c[j];c[j]:=t;
			 t:=d[i];d[i]:=d[j];d[j]:=t;
			 inc(i);dec(j);
		  end;
	  until i>j;
	 if i<rr then sort(i,rr);
	 if ll<j then sort(ll,j);
end;

function okone(i,j,k:longint):boolean;
var temp1,temp2:longint;
begin
  temp1:=(a[j]-a[k])*(b[i]-b[k])-(b[j]-b[k])*(a[i]-a[k]);
  if temp1>=0 then exit(true);
  exit(false);
end;

function oktwo(i,j,k:longint):boolean;
var temp1,temp2:longint;
begin
    temp1:=(c[j]-c[k])*(d[i]-d[k])-(d[j]-d[k])*(c[i]-c[k]);
    if temp1>=0 then exit(true);
   exit(false);
end;

procedure getone(j,k:longint);
var i:longint;
    temp:real;
begin
  if a[j]=a[k] then begin
                        vv[a[j]]:=true;
			f[a[j]]:=b[j];
			f1[a[j]]:=b[k];
		   end;
  if a[j]<a[k] then begin
                        temp:=(b[k]-b[j])/(a[k]-a[j]);
                        for i:=a[j] to a[k] do
                           begin
                            vv[i]:=true;
                            f[i]:=trunc((a[i]-a[j])*temp)+b[j];
                           end;
                         f1[a[k]]:=f[a[k]];
                    end;
  if a[j]>a[k] then  begin
                        temp:=-(b[k]-b[j])/(a[k]-a[j]);
                        for i:=a[j] downto a[k] do
                         begin
                           vv[i]:=true;
                           f1[i]:=trunc((a[j]-a[i])*temp)+b[j];
                         end;
		     end;
end;

procedure gettwo(j,k:longint);
var i:longint;
    temp:real;
begin
  if c[j]=c[k] then begin
                        vv[c[j]]:=true;
			f[c[j]]:=d[j];
			f1[c[j]]:=d[k];
		   end;
  if c[j]<c[k] then begin
                        temp:=(d[k]-d[j])/(c[k]-c[j]);
                        for i:=c[j] to c[k] do
                           begin
                            vv[i]:=true;
                            f[i]:=trunc((c[i]-c[j])*temp)+d[j];
                           end;
                         f1[c[k]]:=f[c[k]];
                    end;
  if c[j]>c[k] then  begin
                        temp:=-(d[k]-d[j])/(d[k]-d[j]);
                        for i:=c[j] downto c[k] do
                         begin
                           vv[i]:=true;
                           f1[i]:=trunc((c[j]-c[i])*temp)+d[j];
                         end;
		     end;
end;

procedure enterone;
var i,j,head,tail,k:longint;
begin
   fillchar(q,sizeof(q),0);
   fillchar(f,sizeof(f),0);
   fillchar(f1,sizeof(f1),0);
   head:=1;tail:=1;q[1]:=1;
   for i:=2 to n do
      begin
	    inc(tail);q[tail]:=i;
		while (tail-1>head) and (okone(q[tail],q[tail-1],q[tail-2])) do begin  q[tail-1]:=q[tail];dec(tail);end;
	  end;
	 head:=tail;
	 for i:=n-1 downto 1 do
	 begin
	    inc(tail);q[tail]:=i;
		while (tail-1>head) and (okone(q[tail],q[tail-1],q[tail-2])) do begin q[tail-1]:=q[tail];dec(tail);end;
	 end;
  fillchar(vv,sizeof(vv),0);
 for i:=2 to tail do
  begin
     j:=q[i-1];k:=q[i];
	 getone(j,k);
  end;
  ans1:=0;
for i:=1 to n do
  if vv[c[i]] then
    if (d[i]>=f[c[i]]) and(d[i]<=f1[c[i]]) then inc(ans1);
end;

procedure entertwo;
var i,j,head,tail,k:longint;
begin
   fillchar(q,sizeof(q),0);
   fillchar(f,sizeof(f),0);
   fillchar(f1,sizeof(f1),0);
   head:=1;tail:=1;q[1]:=1;
   for i:=2 to n do
      begin
	    inc(tail);q[tail]:=i;
		while (tail-1>head) and (oktwo(q[tail],q[tail-1],q[tail-2])) do begin  q[tail-1]:=q[tail];dec(tail);end;
	  end;
	  head:=tail;
	for i:=n-1 downto 1 do
	 begin
	    inc(tail);q[tail]:=i;
		while (tail-1>head) and (oktwo(q[tail],q[tail-1],q[tail-2])) do begin q[tail-1]:=q[tail];dec(tail);end;
	 end;
	 fillchar(vv,sizeof(vv),0);
	for i:=2 to n do
	 begin
	   j:=q[i-1];k:=q[i-2];
	   gettwo(j,k);
	 end;
 ans2:=0;
  for i:=1 to n do
   if vv[a[i]] then
  if (b[i]>=f[a[i]]) and (b[i]<=f1[a[i]]) then inc(ans2);
end;

procedure main;
begin
   qsort(1,n);
   sort(1,n);
   enterone;
   entertwo;
   writeln(ans1,' ',ans2);
end;

begin
   assign(input,'curling.in');reset(input);
   assign(output,'curling.out');rewrite(output);
   init;main;
   close(input);close(output);
end.