比赛 |
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.