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

Why A1=1 B1=2
    A2=2 B2=4
The answer is 5?

Please tell me.Thank you.

Could anyone give me some tricky tests?

I just find all palindromes. make_pair of starting and ending location of each. store result in vector. then use just coin change algo. It gives MLE 56 when using integers and WA 32 or
CRASH 32 when using short. I am crazy about such problem. please anyone let me know what to do.

pp: please!!!

#include <cstdlib>
#include <iostream>

using namespace std;
    int bas = -2000000001;
    int son = 2000000001;
int i,n,j,y,t;
int Fi, Fj, Fn;
int Fibo(int m);
int main(int argc, char *argv[])
{   int h=0;
    cin >> i >> Fi >> j >> Fj >> n;

    if(i > j){swap(i,j); swap(Fi,Fj);}
    t=abs(n);y=abs(i);
    if(n<i && n<0){n=0; i=i+t; j=j+t;}
   else if(i<0 && i<n) { i=0; n=n+y; j=j+y;}

   // cout << i << " " << j <<" " << n;
    int bas = -2000000001;
    int son = 2000000001;
    int m;
if(j==i+1) {h=1;m=Fj;}
   else{

    while(bas <=son)
    {
         m =(bas +son)/2;
        if(Fibo(m)==Fj)
            {  break;}
        else if(Fibo(m)>Fj){
        son= m;}
        else {bas = m ;}
    }

    }

    if(n>i){
   for(int e=i+1;e<n;e++){
   Fn = Fi + m;
   Fi = m;
   m=Fn;}cout << Fn;}
   else if(n==i) cout << Fi;
   else if(n==j) cout << Fj;
   else if(n < i)
   {
     for(int e=n+1;e<=i;e++){
   Fn = m-Fi;
   m = Fi;
   Fi = Fn;

   }
   cout << Fn;
   }
 return 0;
}

int Fibo(int m)
{
    int r=m;
    int fk;
    fk=Fi;
    int ans=0;
    for(int k=i+1; k<j; k++)
    {ans =  fk +r;
    fk=r;
    r=ans;}
    return ans;
}

Why I get always WA2?
Here is my code: http://paste.ubuntu.com/452446/

Please, help me to find out whats wrong!

I'm Wa 4，Who can help me?!!!

Check your vars for type overflow (if KMP check the type of array of pr)

but i still can't pass test 10
what's in it?

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  point=record
    x,y:extended;
  end;

function dist(a,b:point):extended;
  begin
    dist:=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  end;

procedure readp(var a:point);
  begin
    read(a.x,a.y);
  end;

procedure searchXY(a,b,c:extended; var x,y:extended);
  var
    p:extended;
  begin
    p:=(a+b+c)/2;
    if p*p-2*a*b<0 then
      begin
        x:=maxlongint;
        y:=maxlongint;
        exit;
      end;
    x:=(p+sqrt(p*p-2*a*b))/2;
    y:=(p-sqrt(p*p-2*a*b))/2;
  end;

var
  A,B,C:point;
  aa,bb,cc,x,y:extended;
  flagg:integer;

procedure print(a:point; x:extended; b:point; y:extended; c:point);
  var
    CA,CB:point;
  begin
    CA.x:=a.x-c.x;
    CA.y:=a.y-c.y;
    CB.x:=b.x-c.x;
    CB.y:=b.y-c.y;
    if (x/dist(a,c)*CA.x=y/dist(b,c)*CB.x)and(x/dist(a,c)*CA.y=y/dist(b,c)*CB.y) then
      begin
        flagg:=1;
        exit;
      end;
    writeln(x/dist(a,c)*CA.x+c.x:0:9,' ',x/dist(a,c)*CA.y+c.y:0:9);
    writeln(y/dist(b,c)*CB.x+c.x:0:9,' ',y/dist(b,c)*CB.y+c.y:0:9);
  end;

begin
  readp(A);
  readp(B);
  readp(C);
  aa:=dist(B,C);
  bb:=dist(A,C);
  cc:=dist(A,B);
  searchXY(aa,bb,cc,x,y);
  flagg:=0;
  if (x<aa)and(y<bb)and(x<>maxlongint) then
    begin
      writeln('YES');
      print(b,x,a,y,c);
      if flagg=0 then
      halt;
    end;
  flagg:=0;
  if (x<bb)and(y<aa)and(x<>maxlongint) then
    begin
      writeln('YES');
      print(a,x,b,y,c);
      if flagg=0 then
      halt;
    end;
  searchXY(aa,cc,bb,x,y);
  flagg:=0;
  if (x<aa)and(y<cc)and(x<>maxlongint) then
    begin
      writeln('YES');
      print(c,x,a,y,b);
      if flagg=0 then
      halt;
    end;
  flagg:=0;
  if (x<cc)and(y<aa)and(x<>maxlongint) then
    begin
      writeln('YES');
      print(a,x,c,y,b);
      if flagg=0 then
      halt;
    end;
  flagg:=0;
  searchXY(bb,cc,aa,x,y);
  if (x<bb)and(y<cc)and(x<>maxlongint) then
    begin
      writeln('YES');
      print(c,x,b,y,a);
      if flagg=0 then
      halt;
    end;
  flagg:=0;
  if (x<cc)and(y<bb)and(x<>maxlongint) then
    begin
      writeln('YES');
      print(b,x,c,y,a);
      if flagg=0 then
      halt;
    end;
  writeln('NO');
end.

I know that it's "bugcode", but..

ATT

help me!!! What is 4th test?