My solution is O(N^4).

Edited by author 06.08.2009 08:42

Edited by author 06.08.2009 08:42

No subject

Edited by author 28.06.2010 22:13

1000 1000000007
100000 1000000007

thanks

Hi all!

I used Binary Search to solve this problem (because I'm not good at Math) and got AC after WA#2 3 times.

For getting AC, I changed my print line from:

cout << result << endl;
// or print("%f\n", result);

To:

print("%.2f\n", result);

It means you must format your result with 2 precisions after the decimal point, or your result will be something like: 14.99038461538461538461538461538462 (many number after the decimal point).

I hope this would help.
Please reply and notice me if there is something wrong.

MitRo.

I submited many time but all -> wr on test 59.
could anyone help me ??

who is answer it now,i had passed today, simple DP

time复杂度是O(n log^2 n )

Edited by author 29.06.2010 01:10

Edited by author 29.06.2010 01:10

1. there are always solutions.
2. convex polygon. but don't need to find.

Edited by author 10.12.2005 05:18

now AC.

Edited by author 15.10.2006 23:59

I used O(n) with sum and subtract. But it's too slow to AC
Please someone help me.
pp: please

I really couldn't figure out how to solve it. The way I tried even gives the wrong output for the sample! I modelled like this:

Each integer coordinates point represents a node of a graph. There is a edge form point (a, b) to (c, d) iff a >= c and b > d. The edge's weight is equal to the time to go from one point to another one adjacent to the first, which is calculated like this:

if theta is the angle between the segment (a, b)-(c, d) and the x-axis, then due to the gravity there is a 10*cos(theta) acceleration in the x-axis direction. So the time needed to go from (a, b) to (c, d) is sqrt(2*(c-a)/(10*cos(theta))).

Finally, what I do is to run a shortest-path algorithm in this graph. But for the sample my program answers 0.752121.

Does any one knows if ignored any detail? Or maybe if my entire model is wrong?

Thanks!

my answer for '2 100' is 51

How to prove that only for you-know-what cells there exists an answer?

When I use doubele i got wrong in 12.
But after I use BigInteger and got AC.

program ural1317;
const
  maxn=10;
  zero=1e-6;
var
  x,y:array[1..maxn+1]of real;
  n,k,i,ans:longint;
  h,d,a,b,u,v:real;
function cross(xa,ya,xb,yb,xc,yc:real):real;
  var
    x1,y1,x2,y2:real;
  begin
    x1:=xb-xa;y1:=yb-ya;
    x2:=xc-xa;y2:=yc-ya;
    cross:=x1*y2-x2*y1;
  end;
function dist(xa,ya,xb,yb:real):real;
  begin
    dist:=sqrt(sqr(xa-xb)+sqr(ya-yb));
  end;
procedure shoot;
  var
    i:byte;
    l,r:real;
  begin
    for i:=1 to n do
      if cross(a,b,u,v,x[i],y[i])*cross(a,b,u,v,x[i+1],y[i+1])<=0 then begin
        l:=dist(a,b,u,v);
        if l<zero then begin inc(ans);exit;end;
        if d<l then exit;
        r:=abs(cross(a,b,x[i],y[i],x[i+1],y[i+1]))/dist(x[i],y[i],x[i+1],y[i+1]);
        if sqrt(d*d-l*l)/l*r>h then inc(ans);
        exit;
      end;
  end;
begin
  read(n,h);
  for i:=1 to n do
    read(x[i],y[i]);
  x[n+1]:=x[1];y[n+1]:=y[1];
  read(d,a,b,k);
  for i:=1 to k do begin
    readln(u,v);
    shoot;
  end;
  writeln(ans);
end.

Hi,

How come the answer for the test case is three when all the points 0,0 1,1 2,2 3,3 and 4,4 are within 50 meters of the laser. The answer should be 5 ? isn't it ? Also, what are the roles of fence and convex polygon here ? can't seem to get that as well !

Thanks