http://poj.org/problem?id=3227
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define maxn 2000 6 using namespace std; 7 8 int n,h; 9 const double eps=1e-8; 10 int cmp(double x) 11 { 12 if(fabs(x)<eps) return 0; 13 if(x>0) return 1; 14 return -1; 15 } 16 struct point 17 { 18 double x,y; 19 point() {} 20 point(double a,double b):x(a),y(b) {} 21 } p[maxn]; 22 23 double sqr(double x) 24 { 25 return x*x; 26 } 27 28 double dis(point a,point b) 29 { 30 return (sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))); 31 } 32 33 double det(point a,point b,point c,point d) 34 { 35 return (b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x); 36 } 37 38 bool segem(point a,point b,point c,point d,point &e) 39 { 40 double s1=det(a,b,a,c); 41 double s2=det(a,b,a,d); 42 e.x=(c.x*s2-d.x*s1)/(s2-s1); 43 e.y=(c.y*s2-d.y*s1)/(s2-s1); 44 return true; 45 } 46 47 double kk(point a,point b) 48 { 49 return (b.y-a.y)/(b.x-a.x); 50 } 51 int main() 52 { 53 while(scanf("%d%d",&n,&h)!=EOF) 54 { 55 if(n==0&&h==0) break; 56 for(int i=0; i<n; i++) 57 { 58 scanf("%lf%lf",&p[i].x,&p[i].y); 59 } 60 point res; 61 res.x=0; 62 res.y=h; 63 double sum=0; 64 sum+=dis(p[0],p[1]); 65 point key; 66 key=p[1]; 67 for(int i=2; i<n; i++) 68 { 69 double k3=kk(res,p[i]); 70 double k1=kk(p[i],p[i-1]); 71 double k2=kk(res,key); 72 if(k3-k2>eps) 73 { 74 if(k1-k2>=0) 75 { 76 point e; 77 segem(res,key,p[i-1],p[i],e); 78 sum+=dis(e,p[i]); 79 key=p[i]; 80 } 81 } 82 } 83 printf("%.2lf ",sum); 84 } 85 return 0; 86 }