poj 3227. Mountain C语言
标签：表示 while tar amp type 连接 clu pre ons
一道中学的平面几何问题，将目视点与所有其他点连接作为视线，可以看出斜率最大的点后面的山都是看不见的，从前到后计算每点斜率，若靠后点斜率小于靠前点，则看不到两点间山，取到新最大斜率点p时，将原最大斜率点延长，与p及p前一个点的交点即为可以看见的最低位置，求出该交点到p点距离。重复并将距离相加，所得即为所求。
在计算距离的distance函数中，我先定义两个变量dx、dy表示亮点横纵坐标之差，但测试时发现结果不准确。尽量在同一个式子中运算可以减少浮点数运算的误差。
C语言代码
1 #include 2 #include 3
4 typedef struct
5 {
6 double x;
7 double y;
8 } point;
9
10 double getk(point p1, point p2) //求斜率
11 {
12 return ((p2.y - p1.y) * 1.0 / (p2.x - p1.x));
13 }
14
15 double distance(point p1, point p2) //两点距离
16 {
17 // int dx = p1.x - p2.x;
18 // int dy = p1.y - p2.y;
19 return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)) * 1.0;
20 }
21
22 point intersection(point p1, point p2, point q1, point q2) //点斜式求两线交点
23 {
24 double k1 = getk(p1, p2);
25 double k2 = getk(q1, q2);
26 double x = (k1 * p1.x - k2 * q1.x - p1.y + q1.y) * 1.0 / (k1 - k2);
27 double y = k1 * (x - p1.x) + p1.y;
28 point intsec;
29 intsec.x = x;
30 intsec.y = y;
31 return intsec;
32 }
33
34 int main(int argc, char const *argv[])
35 {
36 int pos[1005][1005];
37 int n;
38 double h;
39 point p[1005];
40 while(scanf("%d %lf", &n, &h))
41 {
42 if (n == 0 && h == 0)
43 break;
44 point start;
45 start.x = 0;
46 start.y = h;
47 for (int i = 0; i i)
48 scanf("%lf %lf", &p[i].x, &p[i].y);
49
50 double sum = distance(p[0], p[1]);
51 double maxk = getk(p[1], start);
52 point maxp = p[1]; //斜率最大的点
53 for (int i = 2; i i)
54 {
55 double k = getk(p[i], start);
56 if (k > maxk)
57 {
58 point intsec = intersection(start, maxp, p[i], p[i-1]);
59 sum += distance(intsec, p[i]);
60 maxp = p[i];
61 maxk = k;
62 }
63 }
64 printf("%.2f\n", sum);
65 }
66 return 0;
67 }
poj 3227. Mountain C语言
标签：表示 while tar amp type 连接 clu pre ons
原文地址：https://www.cnblogs.com/timelimitexceed/p/9717494.html
评论