[POJ 2074] Line of Sight【计算几何】
Problem:
| Time Limit: 1000MS | Memory Limit: 30000K |
Description
An architect is very proud of his new home and wants to be sure it can be seen by people passing by his property line along the street. The property contains various trees, shrubs, hedges, and other obstructions that may block the view. For the purpose of this problem, model the house, property line, and obstructions as straight lines parallel to the x axis:
Input
Because each object is a line, it is represented in the input file with a left and right x coordinate followed by a single y coordinate:
< x1 > < x2 > < y >
Where x1, x2, and y are non-negative real numbers. x1 < x2
An input file can describe the architecture and landscape of multiple houses. For each house, the first line will have the coordinates of the house. The second line will contain the coordinates of the property line. The third line will have a single integer that represents the number of obstructions, and the following lines will have the coordinates of the obstructions, one per line.
Following the final house, a line "0 0 0" will end the file.
For each house, the house will be above the property line (house y > property line y). No obstruction will overlap with the house or property line, e.g. if obstacle y = house y, you are guaranteed the entire range obstacle[x1, x2] does not intersect with house[x1, x2].
< x1 > < x2 > < y >
Where x1, x2, and y are non-negative real numbers. x1 < x2
An input file can describe the architecture and landscape of multiple houses. For each house, the first line will have the coordinates of the house. The second line will contain the coordinates of the property line. The third line will have a single integer that represents the number of obstructions, and the following lines will have the coordinates of the obstructions, one per line.
Following the final house, a line "0 0 0" will end the file.
For each house, the house will be above the property line (house y > property line y). No obstruction will overlap with the house or property line, e.g. if obstacle y = house y, you are guaranteed the entire range obstacle[x1, x2] does not intersect with house[x1, x2].
Output
For each house, your program should print a line containing the length of the longest continuous segment of the property line from which the entire house can be to a precision of 2 decimal places. If there is no section of the property line where the entire house can be seen, print "No View".
Sample Input
2 6 6 0 15 0 3 1 2 1 3 4 1 12 13 1 1 5 5 0 10 0 1 0 15 1 0 0 0
Sample Output
8.80 No View
Source
Mid-Atlantic 2004
Solution:
首先注意以下几点：
- 视线恰好穿过障碍物(obstruction)边缘时也算被遮挡，即答案不会输出 0.00 ，取而代之的应该是 No View 。
- 对于不严格在房子(house)和地界线(property line)之间的障碍物直接忽略。
计算每个障碍物能挡住的区间 [lY, rY]（如图所示，不考虑其他障碍物时，<lY 的部分和 >rY 的部分可以看到整个房子）。
将障碍物按 lY 排序，从左到右扫描记下当前最大rY，并即时计算并更新最大连续区间。
计算时要注意 lY 和 rY 是否超出地界线边缘，可以简单地规约为以下公式：
- maxsight = max{min(curlY, pl.Y2) - max(maxrY, pl.Y1)}，其中 curlY 为当前障碍物的 lY，maxrY 为先前所有障碍物中 rY 的最大值。
实现时，为计算直线斜率和函数值方便，可以将 x 和 y 坐标交换。
Code: O(Tnlogn) [188K, 0MS]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<algorithm>
#define eps 1e-8
#define dmax 1e10
using namespace std;
inline int dsgn(double x){
if(fabs(x) <= eps) return 0;
return x < 0 ? -1 : 1;
}
int n;
struct Object{ // For slope calculation, X-coordinate is exchanged with Y-coordinate
double Y1, Y2, X;
// Declarations and implementations below are only available for "obstructions"
double lY, rY;
// lY is the leftest Y-coordinate that can see the left of House exactly through the right of this obstruction
// rY is the rightest Y-coordinate that can see the right of House exactly through the left of this obstruction
inline bool operator < (const Object &obj2) {return dsgn(lY - obj2.lY) < 0;}
} hs, pl, obs[55];
struct Line{
double k, b;
inline bool Construct(const double &PX, const double &PY, const double &QX, const double &QY){
if(dsgn(PX - QX) == 0) return 1; // The slope is infinite, construction fails
k = (QY - PY) / (QX - PX);
b = PY - k * PX;
assert(dsgn(k * QX + b - QY) == 0);
return 0;
}
inline double calcY(const double &x) {return k * x + b;}
} lin;
int main(){
while(scanf("%lf%lf%lf", &hs.Y1, &hs.Y2, &hs.X) && (dsgn(hs.Y1) > 0 || dsgn(hs.Y2) > 0 || dsgn(hs.X) > 0)){
scanf("%lf%lf%lf%d", &pl.Y1, &pl.Y2, &pl.X, &n);
for(register int i = 1; i <= n; i++){
scanf("%lf%lf%lf", &obs[i].Y1, &obs[i].Y2, &obs[i].X);
if(dsgn(obs[i].X - hs.X) >= 0 || dsgn(obs[i].X - pl.X) <= 0) i--, n--;
// If the obstructions are not between the house and the property line, ignore it
}
for(register int i = 1; i <= n; i++){
lin.Construct(obs[i].X, obs[i].Y1, hs.X, hs.Y2);
obs[i].lY = lin.calcY(pl.X);
lin.Construct(obs[i].X, obs[i].Y2, hs.X, hs.Y1);
obs[i].rY = lin.calcY(pl.X);
}
sort(obs + 1, obs + n + 1);
double maxsight = -dmax, rmax = pl.Y1;
maxsight = max(maxsight, min(obs[1].lY, pl.Y2) - rmax);
for(register int i = 1; i < n; i++){
rmax = max(rmax, obs[i].rY);
maxsight = max(maxsight, min(obs[i + 1].lY, pl.Y2) - rmax);
}
rmax = max(rmax, obs[n].rY);
maxsight = max(maxsight, pl.Y2 - rmax);
if(dsgn(maxsight) <= 0) puts("No View"); // Only one point is considered as "No View", not "0.00"
else printf("%.2f\n", maxsight);
}
return 0;
}
发表评论