fork(1) download 
  1. {
  2.  Author:wzx961008
  3.  Problem:sgu 345-Revolution
  4.  Verdict:Accepted
  5.  Language:PASCAL
  6.  Run Time:0.765s
  7.  Submission Date:26.08.11 08:25
  8. }
  9. {$MODE Delphi}
  10. uses math;
  11. const error=1e-8; maxn=50000; oo=1e10;
  12. type point=record x,y:extended; end;
  13. var pt,convex:array[1..maxn+1]of point;
  14.     sum:array[1..maxn+1]of extended;
  15.     fs:array[1..maxn*2+2]of point;
  16.     n,m,top:longint;
  17.     s:extended;
  18.     origin:point;
  19. procedure swap(var p1,p2:point);
  20. var t:point;
  21. begin
  22.  t:=p1; p1:=p2; p2:=t;
  23. end;
  24. function cross(p11,p12,p21,p22:point):extended;
  25. var x1,y1,x2,y2:extended;
  26. begin
  27.  x1:=p12.x-p11.x;
  28.  y1:=p12.y-p11.y;
  29.  x2:=p22.x-p21.x;
  30.  y2:=p22.y-p21.y;
  31.  cross:=x1*y2-x2*y1;
  32. end;
  33. function dist(p1,p2:point):extended;
  34. begin
  35.  dist:=sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
  36. end;
  37. procedure qsort_polar_angle(l,r:longint);
  38. var i,j:longint;
  39.     m:point;
  40.     crs1,crs2,dstm:extended;
  41. begin
  42.  i:=l; j:=r; m:=pt[l+random(r-l)];
  43.  repeat
  44.   dstm:=dist(pt[1],m);
  45.   repeat
  46.    crs1:=cross(pt[1],m,pt[1],pt[i]);
  47.    if not((crs1<-error)or((abs(crs1)<error)and(dstm>dist(pt[1],pt[i])))) then break;
  48.    inc(i);
  49.   until false;
  50.   repeat
  51.    crs2:=cross(pt[1],pt[j],pt[1],m);
  52.    if not((crs2<-error)or((abs(crs2)<error)and(dist(pt[1],pt[j])>dstm))) then break;
  53.    dec(j);
  54.   until false;
  55.   if i<=j then begin
  56.    swap(pt[i],pt[j]);
  57.    inc(i); dec(j);
  58.   end;
  59.  until i>j;
  60.  if l<j then qsort_polar_angle(l,j);
  61.  if i<r then qsort_polar_angle(i,r);
  62. end;
  63. procedure get_point;
  64. var i:longint;
  65. begin
  66.  readln(n);
  67.  for i:=1 to n do begin
  68.   readln(pt[i].x,pt[i].y);
  69.   if (pt[i].y<pt[1].y)or((abs(pt[i].y-pt[1].y)<error)and(pt[i].x<pt[1].x)) then swap(pt[1],pt[i]);
  70.  end;
  71. end;
  72. procedure get_convex;
  73. var p,i:longint;
  74. begin
  75.  for i:=1 to n do begin
  76.   inc(top); convex[top]:=pt[i];
  77.   if top>2 then begin
  78.    p:=top-1;
  79.    while (p>1)and(sign(cross(convex[p-1],convex[p],convex[p],convex[top]))<=0) do dec(p);
  80.    top:=p+1; convex[top]:=pt[i];
  81.   end;
  82.  end;
  83. end;
  84. function qd(p:point):longint;
  85. begin
  86.  if (p.x>0)and(p.y>=0) then begin qd:=1; exit; end;
  87.  if (p.x<=0)and(p.y>0) then begin qd:=2; exit; end;
  88.  if (p.x<0)and(p.y<=0) then begin qd:=3; exit; end;
  89.  if (p.x>=0)and(p.y<0) then begin qd:=4; exit; end;
  90. end;
  91. function smler_pa(p11,p12,p21,p22:point):boolean;
  92. var vc1,vc2:point;
  93.     qd1,qd2:longint;
  94. begin
  95.  vc1.x:=p12.x-p11.x; vc1.y:=p12.y-p11.y;
  96.  vc2.x:=p22.x-p21.x; vc2.y:=p22.y-p21.y;
  97.  qd1:=qd(vc1); qd2:=qd(vc2);
  98.  if qd1<>qd2 then begin smler_pa:=qd1<qd2; exit; end;
  99.  smler_pa:=cross(p11,p12,p21,p22)>=0;
  100. end;
  101. procedure init;
  102. var i:longint;
  103. begin
  104.  get_point;
  105.  randomize;
  106.  qsort_polar_angle(2,n);
  107.  get_convex;
  108.  for i:=1 to top do begin
  109.   fs[i]:=convex[i];
  110.   fs[i+top]:=convex[i];
  111.  end;
  112.  sum[1]:=0;
  113.  for i:=2 to top do sum[i]:=sum[i-1]+cross(origin,convex[i-1],origin,convex[i]);
  114.  s:=sum[top]+cross(origin,convex[top],origin,convex[1]);
  115. end;
  116. function itst(p1,p2:point; a,b,c:extended; var ip:point):boolean;
  117. var aa,bb,cc,tmp:extended;
  118. begin
  119.  itst:=false;
  120.  if sign((a*p1.x+b*p1.y+c)*(a*p2.x+b*p2.y+c))<=0 then begin
  121.   itst:=true;
  122.   aa:=p1.y-p2.y; bb:=p2.x-p1.x; cc:=p1.x*p2.y-p2.x*p1.y;
  123.   tmp:=bb*a-b*aa; if sign(tmp)=0 then begin itst:=false; exit; end;
  124.   ip.x:=(b*cc-c*bb)/tmp;
  125.   ip.y:=(c*aa-a*cc)/tmp;
  126.  end;
  127. end;
  128. procedure main;
  129. var i,fp1n,fp2n,cp1n,cp2n,i1s1,i1s2,i2s1,i2s2,tmp:longint;
  130.     p1,p2,ip,ip1,ip2:point;
  131.     a,b,c,s1:extended;
  132.     b1,b2,bb:boolean;
  133. function next(x:longint):longint;
  134. begin
  135.  if x=top then next:=1 else next:=x+1;
  136. end;
  137. function last(x:longint):longint;
  138. begin
  139.  if x=1 then last:=top else last:=x-1;
  140. end;
  141. function check(p1,p2:point):boolean;
  142. begin
  143.  check:=(abs(p1.x-p2.x)<error)and(abs(p1.y-p2.y)<error);
  144. end;
  145. function binary_search(p1,p2:point):longint;
  146. var l,r,m:longint;
  147.     b1,b2:boolean;
  148.     vec:point;
  149. begin
  150.  vec.x:=p2.x-p1.x; vec.y:=p2.y-p1.y;
  151.  if (cross(origin,vec,convex[top],convex[1])<=0)and(cross(origin,vec,convex[1],convex[2])>=0) then begin binary_search:=1; exit; end;
  152.  if (cross(origin,vec,convex[top-1],convex[top])<=0)and(cross(origin,vec,convex[top],convex[1])>=0) then begin binary_search:=top; exit; end;
  153.  l:=1; r:=top;
  154.  while true do begin
  155.   m:=(l+r) shr 1;
  156.   b1:=smler_pa(convex[m-1],convex[m],origin,vec);
  157.   b2:=smler_pa(origin,vec,convex[m],convex[m+1]);
  158.   if (b1)and(b2) then begin binary_search:=m; exit; end;
  159.   if (b1)and(not(b2)) then l:=m;
  160.   if (not(b1))and(b2) then r:=m;
  161.  end;
  162. end;
  163. function trinary_search(l,r:longint):longint;
  164. var ll,rr,t1,t2,t,ret:longint;
  165.     fd1,fd2,fd3,min:extended;
  166. begin
  167.  ll:=l; rr:=r;
  168.  if r<l then rr:=rr+top;
  169.  while true do begin
  170.   t:=(rr-ll) div 3; t1:=ll+t; t2:=rr-t;
  171.   fd1:=abs(a*fs[t1].x+b*fs[t1].y+c);
  172.   fd2:=abs(a*fs[t2].x+b*fs[t2].y+c);
  173.   if rr-ll<=2 then begin
  174.    min:=oo;
  175.    if rr-ll=2 then begin
  176.     fd3:=abs(a*fs[ll+1].x+b*fs[ll+1].y+c);
  177.     if fd3<min then begin
  178.      min:=fd3; ret:=ll+1;
  179.     end;
  180.    end;
  181.    if fd1<min then begin
  182.     min:=fd1; ret:=ll;
  183.    end;
  184.    if fd2<min then begin
  185.     min:=fd2; ret:=rr;
  186.    end;
  187.    trinary_search:=ret; exit;
  188.   end;
  189.   if fd1<fd2 then rr:=t2 else ll:=t1;
  190.  end;
  191. end;
  192. begin
  193.  readln(m);
  194.  for i:=1 to m do begin
  195.   readln(p1.x,p1.y,p2.x,p2.y);
  196.   a:=p1.y-p2.y; b:=p2.x-p1.x; c:=p1.x*p2.y-p2.x*p1.y;
  197.   fp1n:=binary_search(p1,p2);
  198.   fp2n:=binary_search(p2,p1);
  199.   cp1n:=trinary_search(fp1n,fp2n); if cp1n>top then cp1n:=cp1n-top;
  200.   cp2n:=trinary_search(fp2n,fp1n); if cp2n>top then cp2n:=cp2n-top;
  201.   b1:=true; b2:=true;
  202.   if itst(convex[last(cp1n)],convex[cp1n],a,b,c,ip) then begin
  203.    ip1:=ip; b1:=false; i1s1:=last(cp1n); i1s2:=cp1n;
  204.   end;
  205.   if itst(convex[cp1n],convex[next(cp1n)],a,b,c,ip) then begin
  206.    if b1 then begin ip1:=ip; b1:=false; i1s1:=cp1n; i1s2:=next(cp1n); end;
  207.    if not(check(ip1,ip))and(not(b1)) then begin
  208.     ip2:=ip; b2:=false; i2s1:=cp1n; i2s2:=next(cp1n);
  209.    end;
  210.   end;
  211.   if itst(convex[last(cp2n)],convex[cp2n],a,b,c,ip) then begin
  212.    if b1 then begin ip1:=ip; b1:=false; i1s1:=last(cp2n); i1s2:=cp2n; end;
  213.    if not(check(ip1,ip))and(not(b1)) then begin
  214.     ip2:=ip; b2:=false; i2s1:=last(cp2n); i2s2:=cp2n;
  215.    end;
  216.   end;
  217.   if itst(convex[cp2n],convex[next(cp2n)],a,b,c,ip) then begin
  218.    if b1 then begin ip1:=ip; b1:=false; i1s1:=cp2n; i1s2:=next(cp2n); end;
  219.    if not(check(ip1,ip))and(not(b1)) then begin
  220.     ip2:=ip; b2:=false; i2s1:=cp2n; i2s2:=next(cp2n);
  221.    end;
  222.   end;
  223.   if (b1)or(b2) then begin writeln('0.000000'); continue; end;
  224.   if i1s1>i1s2 then begin tmp:=i1s1; i1s1:=i1s2; i1s2:=tmp; end;
  225.   if i2s1>i2s2 then begin tmp:=i2s1; i2s1:=i2s2; i2s2:=tmp; end;
  226.   bb:=true;
  227.   if ((i1s1=1)and(i1s2=top))and(bb) then begin s1:=sum[i2s1]+(cross(origin,convex[i2s1],origin,ip2)+cross(origin,ip2,origin,ip1)+cross(origin,ip1,origin,convex[1])); bb:=false; end;
  228.   if ((i2s1=1)and(i2s2=top))and(bb) then begin s1:=sum[i1s1]+(cross(origin,convex[i1s1],origin,ip1)+cross(origin,ip1,origin,ip2)+cross(origin,ip2,origin,convex[1])); bb:=false; end;
  229.   if (i1s2<=i2s1)and(bb) then begin s1:=(sum[i2s1]-sum[i1s2])+(cross(origin,convex[i2s1],origin,ip2)+cross(origin,ip2,origin,ip1)+cross(origin,ip1,origin,convex[i1s2])); bb:=false; end;
  230.   if (i2s2<=i1s1)and(bb) then begin s1:=(sum[i1s1]-sum[i2s2])+(cross(origin,convex[i1s1],origin,ip1)+cross(origin,ip1,origin,ip2)+cross(origin,ip2,origin,convex[i2s2])); bb:=false; end;
  231.   writeln(min(s-s1,s1)/2:0:6);
  232.  end;
  233. end;
  234. begin
  235.  init;
  236.  main;
  237. end.
stdin 
5
0 0
0 5
0 10
10 10
10 0
4
0 0 10 10
9 10 10 9
10 -1 12 11
10 10 0 5
compilation info 
Free Pascal Compiler version 2.2.0 [2009/11/16] for i386
Copyright (c) 1993-2007 by Florian Klaempfl
Target OS: Linux for i386
Compiling prog.pas
prog.pas(18,5) Warning: Variable "origin" read but nowhere assigned
Linking prog
236 lines compiled, 0.1 sec
1 warning(s) issued
stdout 
50.000000
0.500000
0.000000
25.000000
https://ideone.com/5hRX8
language:
Pascal (fpc 3.0.4)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!