Discussion of Problem 1317. HailThe 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); } } Edited by author 12.11.2010 20:11 Don't use the crutch if (n == 3), it causes wa6 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. 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. Your algo to find intersection point is wrong. Use algo to find intersection point of 2 lines with modifications. 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 Laser can't shoot through polygon and height of wall is important. 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. It depends on the way use solve the problem. If you do all calculations in integers, any EPS from 1e-0 to 1e-15 will give right answer =) If you do all calculations in integers, any EPS from 1e-0 to 1e-15 will give right answer =) How can you do all calculations in integers if there are a lot of real numbers in input and no limits on number of digits after decimal point? 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? First test have not to be test from the statement. There are some problems on timus where first test exactly different. 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. In english version of statement is said that inside (it is really so) But in russian one isn't said anything about it. 2Admins: please, fix this bug! My program always wa on test3, could you send me your program? |
|