|
|
back to boardWhat's the test 8 Posted by yuyan 18 Mar 2009 06:07 Why I WA on #8?I can't find what's wrong with my program. Here is my code: program jamaica; const maxn=310; var k,b,l:array [0..maxn*maxn] of extended; x,y:array [0..maxn] of int64; i,j,m,n,min,max:longint; ans,d:double; procedure init; begin readln(n); for i:=1 to n do readln(x[i],y[i]); end; procedure qsort(head,tail:longint); var i,j,t,k:longint; begin if head>=tail then exit; i:=head;j:=tail; t:=x[(i+j) shr 1]; repeat while x[j]>t do dec(j); while x[i]<t do inc(i); if i<=j then begin k:=x[i];x[i]:=x[j];x[j]:=k; k:=y[i];y[i]:=y[j];y[j]:=k; inc(i);dec(j); end; until i>=j; qsort(head,j); qsort(i,tail); end; procedure sort(head,tail:longint); var i,j:longint; x,y,t:double; begin if head>=tail then exit; i:=head;j:=tail; x:=k[(i+j) shr 1];y:=b[(i+j) shr 1]; repeat while (k[j]-x>1e-8) or (abs(k[j]-x)<1e-8) and (b[j]-y>1e-8) do dec(j); while (k[i]-x<-1e-8) or (abs(k[i]-x)<1e-8) and (b[i]-y<-1e-8) do inc(i); if i<=j then begin t:=k[i];k[i]:=k[j];k[j]:=t; t:=b[i];b[i]:=b[j];b[j]:=t; t:=l[i];l[i]:=l[j];l[j]:=t; inc(i);dec(j); end; until i>=j; sort(head,j); sort(i,tail); end; procedure solve; begin qsort(1,n); ans:=0; min:=y[1];max:=y[1]; for i:=2 to n do if x[i]<>x[i-1] then begin ans:=ans+max-min; max:=y[i];min:=y[i]; end else begin if y[i]>max then max:=y[i]; if y[i]<min then min:=y[i]; end; ans:=ans+max-min; m:=0; for i:=1 to n-1 do for j:=i+1 to n do if x[i]<>x[j] then begin inc(m);k[m]:=(y[j]-y[i])/(x[j]-x[i]);b[m]:=y[i]-k[m]*x[i]; l[m]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])); end; sort(1,m); d:=l[1]; for i:=2 to m do if (k[i]<>k[i-1]) or (b[i]<>b[i-1]) then begin ans:=ans+d; d:=l[i]; end else begin if l[i]>d then d:=l[i]; end; ans:=ans+d; end; begin init; solve; writeln(round(ans)); end. |
|
|