poj 3277 Mountains
11207 ワード
http://poj.org/problem?id=3227
View Code
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 }
View Code