题意：从一条线段(property)上观察另一与之平行的线段(house)，其中有很多与它们都平行的线段(障碍物)，求在property得可见整条线段house的最长连续范围的长度。
类别：直线交
思路：求出线段house对于每条障碍物在线段property在的最大投影，投影即为在线段property上，被这条障碍物遮蔽，而无法看见整条线段house的范围。然后求出线段property上没有被投影到的最长的连续区间长度即为所求答案。另外，要注意先排除掉位置不是在house和property之间的障碍物。
View Code
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; #define eps 1e-8 struct point { double x, y; }; struct seg { point s, e; }h, pro, obs[101]; struct data { double l, r; }d[101]; int cmp(data a, data b) { if(a.l == b.l) return a.r < b.r; return a.l < b.l; } int n; double l[101], r[101]; int dblcmp(double x) { if( fabs(x) < eps ) return 0; return x > 0 ? 1 : -1; } double det(double x1, double y1, double x2, double y2) { return x1 * y2 - y1 * x2; } double cross(point o, point a, point b) { return det(a.x - o.x, a.y - o.y, b.x - o.x, b.y - o.y); } double seg_cross(point a, point b, point c, point d) //根据题目要求适当修改直线交的模板 { //两直线一定规范相交 point tmp; int d1, d2; double s1, s2; s1 = cross(a, b, c); s2 = cross(a, b, d); tmp.x = ( s2 * c.x - s1 * d.x ) / (s2 - s1); tmp.y = ( s2 * c.y - s1 * d.y ) / (s2 - s1); return tmp.x; } int main() { int i, j; while( ~scanf("%lf%lf%lf", &h.s.x, &h.e.x, &h.s.y) ) { if(!h.s.x && !h.e.x && !h.s.y)break; h.e.y = h.s.y; scanf("%lf%lf%lf", &pro.s.x, &pro.e.x, &pro.s.y); pro.e.y = pro.s.y; scanf("%d", &n); for(i = 0; i < n; i++) { scanf("%lf%lf%lf", &obs[i].s.x, &obs[i].e.x, &obs[i].s.y); if( obs[i].s.y > h.s.y || obs[i].s.y < pro.s.y ) { n--; i--; continue; } obs[i].e.y = obs[i].s.y; } if(!n) {printf("%.2f\n", pro.e.x - pro.s.x); continue; } //没有障碍物 int num = 0; bool flag = false; for(i = 0; i < n; i++) { d[num].l = seg_cross(h.e, obs[i].s, pro.s, pro.e); d[num].r = seg_cross(h.s, obs[i].e, pro.s, pro.e); if(d[num].r < pro.s.x || d[num].l > pro.e.x) continue; //删除 投影在property的外面的 if(d[num].l < pro.s.x && d[num].r > pro.e.x){ flag = true; break; } //有障碍遮住了全部 if(d[num].l < pro.s.x ) d[num].l = pro.s.x; if(d[num].r > pro.e.x ) d[num].r = pro.e.x; num++; } if(flag) { printf("No View\n"); continue; } //遮住了全部 sort(d, d + num, cmp); //合并遮住的各个区间 l[0] = d[0].l; r[0] = d[0].r; int cnt = 0; for(i = 1; i < num; i++) { if(r[cnt] >= d[i].l) r[cnt] = max(r[cnt], d[i].r); //更新右边界 else { cnt++; l[cnt] = d[i].l; r[cnt] = d[i].r; } } double ans = max( l[0] - pro.s.x, pro.e.x - r[cnt]); //两端可见长度取最大 for(i = 0; i < cnt; i++) ans = max( ans, l[i+1] - r[i]); if(dblcmp(ans) == 1) printf("%.2f\n", ans); else printf("No View\n"); } return 0; }