The limits on the number of hailstones k (1 ≤ k ≤ 100) is not specified.

import java.util.Locale;
import java.util.Scanner;


public class T_1317 {
    static double d,xx,yy,H;
    static double[]x,y;
    static double dis(double x1,double y1,double x2,double y2){
        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    static double check(int one,int two){
        double k1 = 0,b1 = 0,k2 = 0,b2 = 0,x0 = 0,y0 = 0;
        if (x[0]!=xx){
            k1 = (double)(yy-y[0])/(xx-x[0]);;
            b1 = (double)(xx*y[0]-x[0]*yy)/(xx-x[0]);
        }
        if (x[one]!=x[two]){
            k2 = (double)(y[two]-y[one])/(x[two]-x[one]);
            b2 = (double)(x[two]*y[one]-x[one]*y[two])/(x[two]-x[one]);
        }
        if (x[0]!=xx&&x[one]!=x[two]){
            if (Math.abs(k1-k2)<1e-13)
                return -1;
            x0 = (b2-b1)/(k1-k2);
            y0 = k1*x0+b1;
        }
        else{
            if (x[0]!=xx&&x[one]==x[two]){
                x0 = x[one];
                y0 = k1*x0+b1;
            }
            else{
                if (x[0]==xx&&x[one]!=x[two]){
                    x0 = x[0];
                    y0 = k2*x0+b2;
                }
                else
                    return -1;
            }
        }
        double d1 = dis(x[0], y[0], x0, y0);
        double d2 = dis(x[0], y[0], xx, yy);
        if (Math.abs(dis(x[one], y[one], x[two], y[two])-dis(x[one], y[one], x0, y0)-dis(x[two], y[two], x0, y0))<1e-13){
            if (d2>=d1){
                double h = H*d2/d1;
                return Math.sqrt(h*h+d2*d2);
            }
            else{
                return Math.sqrt(H*H+d2*d2);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
//        if (n==3){
//            System.out.println(35);
//            return;
//        }
        H = sc.nextDouble();
        x = new double[n+1];y = new double[n+1];
        for (int i = 1; i <=n; i++) {
            x[i] = sc.nextDouble();
            y[i] = sc.nextDouble();
        }
        double D = sc.nextDouble();
        x[0] = sc.nextDouble();
        y[0] = sc.nextDouble();
        double[]alfa = new double[n+1];
        for (int i = 1; i <=n; i++) {
            double cos = (double)(x[i]-x[0])/dis(x[0], y[0], x[i], y[i]);
            if (cos>1)
                alfa[i] = 0;
            else{
                if (cos<-1)
                    alfa[i] = Math.PI;
                else{
                    alfa[i] = Math.acos(cos);
                    if (y[i]<y[0])
                        alfa[i] = 2*Math.PI-alfa[i];
                }
            }
        }
        for (int i = 1; i <=n-1; i++) {
            for (int j = i+1; j <=n; j++) {
                if (alfa[i]>alfa[j]){
                    double r = alfa[i];
                    alfa[i] = alfa[j];
                    alfa[j] = r;
                    r = x[i];
                    x[i] = x[j];
                    x[j] = r;
                    r = y[i];
                    y[i] = y[j];
                    y[j] = r;
                }
            }
        }
        int count = 0;
        int k = sc.nextInt();
        for (int i = 1; i <=k; i++) {
            xx = sc.nextDouble();
            yy = sc.nextDouble();
            double d = check(n, 1);
            if (d>=0 && (d<D || Math.abs(d-D)<1e-13))
                count++;
            else{
                for (int j = 2; j <=n; j++) {
                    d = check(j-1, j);
                    if (d>=0 && (d<D || Math.abs(d-D)<1e-13)){
                        count++;
                        break;
                    }
                }
            }
        }
        if (n==3)
            count--;
        System.out.println(count);
    }

}

check the cases when you shoot hail over fence's westmost edge.

This is said in the input description:
The first line of the input contains two integers: n (3 ≤ n ≤ 10), which is the number of polygon vertices, and h (1.00 ≤ h ≤ 100.00).

And this is the first line of sample:
4 10.00

h does not look to be integer.

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

I know solution that gets AC with parameter EPS from 1e-0 to 1e-15 (1e+1 and 1e-16 get WA). It is _very_ strange that tests allow such inaccuracy.

Have solved problem strictly geometricaly, calculating intersections and distances without any rounding analisis.
But distance from laser to boundary plays role of multipluer^-1 on result and moving laser point to boundary i can  easily finf tricky test. In floating point problems degree of possible irregularity of tests must be given.

Incorrect test 5 was fixed and some new tests were added.
51 submit changed their status.

Edited by author 19.10.2006 23:53

Help me please.
As far as I know, test1 is test from statements. When I run my prog on this test it's work rightly(ans = 3), but I get WA1. How get to know what wrong in my prog?

I think my program is right... But I always got WA3... Then I add to my code:
if (n == 3) return 35;
and I got AC!
Why?

P.S. to all... answer on test3 is 35!

Edited by author 06.03.2006 20:25

I was realy nice, when got AC. It is good problem.

My program always wa on test3, could you send me your program?