挺好的一道計算幾何題目
題目大意是：給一條線段代表房子，給一條線段代表路，給一些障礙物，求在路上能完全看到房子的最長連續長度
題目中所有線段都是和x軸平行的
兩個難點
1、利用相似三角形，求出再房子和障礙物連線在路上的交點
2、判斷線段的相交方式，并切割線段
這些問題都解決了之后，就是寫代碼了
1 /*
2 * SOUR:pku 2074
3 * ALGO:computional geometry
4 * DATE: Thu, 15 Oct 2009 23:22:48 +0800
5 * COMM:3
6 * */
7 #include<iostream>
8 #include<cstdio>
9 #include<cstdlib>
10 #include<cstring>
11 #include<algorithm>
12 #include<vector>
13 #include<cassert>
14 #include<cmath>
15 using namespace std;
16 typedef long long LL;
17 const int maxint = 0x7fffffff;
18 const long long max64 = 0x7fffffffffffffffll;
19 template<class T>void show(T a, int n){for(int i=0;i<n;++i)cout<<a[i]<<' ';cout<<endl;}
20 template<class T>void show(T a,int r,int l){for(int i=0;i<r;++i)show(a[i],l);cout<<endl;}
21 #define pr(x
) fprintf(stderr, x)
22 /* #define pr(x) for(;0;) */
23 const int N = 512;
24 const double eps = 1e-7;
25 struct NODE {
26 double x1,x2,y;
27 NODE(){}
28 NODE(double a,double b){ x1 = a,x2 = b; }
29 }h,ob,root;
30 vector<NODE> g[N];
31 int n,top,pt;
32
33
34 struct point_t{
35 double x,y;
36 point_t(){}
37 point_t(double a,double b){
38 x = a,y = b;
39 }
40 };
41 point_t operator +(point_t a,point_t b) { return point_t(a.x + b.x,a.y + b.y); }
42 point_t operator -(point_t a,point_t b) { return point_t(a.x - b.x,a.y - b.y); }
43 point_t operator *(point_t a,double b) { return point_t(a.x * b,a.y * b); }
44 point_t operator /(point_t a,double b) { return point_t(a.x / b,a.y / b); }
45 double sqr(double x) {return x * x;}
46 double dist(point_t a) { return sqrt(sqr(a.x) + sqr(a.y)); }
47 double dist(point_t a,point_t b) { return dist(a-b); }
48
49 void cut(int idx,double v1,double v2)
50 {
51 int i,j,k;
52 for(i = 0;i < g[idx-1].size();i++) {
53 if(v1 <= g[idx-1][i].x1 && v2 >= g[idx-1][i].x2) {
54 }else if(v1 <= g[idx-1][i].x1 && v2 > g[idx-1][i].x1 && v2 <= g[idx-1][i].x2) {
55 g[idx].push_back(NODE(v2,g[idx-1][i].x2));
56 }else if(v1 >= g[idx-1][i].x1 && v1 < g[idx-1][i].x2 && v2 >= g[idx-1][i].x2) {
57 g[idx].push_back(NODE(g[idx-1][i].x1,v1));
58 }else if(v1 >= g[idx-1][i].x1 && v2 <= g[idx-1][i].x2) {
59 g[idx].push_back(NODE(g[idx-1][i].x1,v1));
60 g[idx].push_back(NODE(v2,g[idx-1][i].x2));
61 }else {
62 g[idx].push_back(g[idx-1][i]);
63 }
64 }
65 }
66
67
68 point_t cacu(point_t a,point_t b)
69 //b為ob,a為h
70 {
71 assert(h.y - root.y >= 0);
72 assert(h.y - ob.y >= 0);
73 return a + (b - a) * (h.y - root.y) / (h.y - ob.y);
74 }
75
76 int main()
77 {
78 int i,j,k;
79 while(scanf("%lf%lf%lf",&h.x1,&h.x2,&h.y) && (h.x1 || h.x2 || h.y)) {
80 scanf("%lf%lf%lf",&root.x1,&root.x2,&root.y);
81 scanf("%d",&n);
82 for(i = 0;i < N;i++) {
83 g[i].clear();
84 }
85 g[0].push_back(root);
86 for(i = 1,j = 0;i <= n;i++) {
87 scanf("%lf%lf%lf",&ob.x1,&ob.x2,&ob.y);
88 if(ob.y < h.y && ob.y > root.y) {
89 point_t v1 = cacu(point_t(h.x2,h.y) , point_t(ob.x1,ob.y));
90 point_t v2 = cacu(point_t(h.x1,h.y) , point_t(ob.x2,ob.y));
91 //printf("<%f,%f> <%f,%f>\n",v1.x,v1.y,v2.x,v2.y);
92 assert(v1.x <= v2.x && fabs(v1.y - v2.y) < eps);
93 cut(++j,v1.x,v2.x);
94 }
95 }
96 double res = 0;
97 for(i = 0;i < g[j].size();i++) {
98 res = max(res,g[j][i].x2 - g[j][i].x1);
99 }
100 if(res < eps) {
101 printf("No View\n");
102 }else {
103 printf("%.2f\n",res);
104 }
105 }
106 return 0;
107 }
108
109
1Y感覺很不錯