嘟嘟嘟
題意：用一條水準線段表示以棟房子：((x_0, y_0)(x_0', y_0))。然後有一條低于房子的水準線段(l_0)，代表你可以到的位置。接下來輸入一個數(n)，一下(n)行每行(3)個數，用一條水準線段代表障礙物。求你在(l_0)上能看到房子的最大連續長度。（看到房子指房子完全沒被擋上）
剛開始自己(yy)了一個(O(n ^ 2))的算法，結果(TLE)了……誰叫這題不告訴我資料範圍的。
正解比較有意思：我們要逆向思維：對于一個障礙物，求出它能遮擋的範圍，那麼最後的答案就是沒被遮擋的區間長度的最大值。
遮擋的範圍畫個圖就明白了：
則([N, M])就是被遮擋的區間，然後用叉積求交點即可。
那麼現在我們就得到了一堆區間（可能重疊），然後想括号比對一樣跑一邊，如果目前棧空，就那(a _ {i + 1} - a _ i)更新答案。
需要注意的是([N, M])可能在直線(l_0)之外，這時候那(l_0)兩個端點限制(N, M)即可，具體看代碼。
還有一點就是區間的頭和尾的地方要單獨算一下，即(a _ 1 - L)和(R - a _ n)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 5e4 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n;
struct Vec
{
db x, y;
db operator * (const Vec& oth)const
{
return x * oth.y - oth.x * y;
}
};
struct Point
{
db x, y;
Vec operator - (const Point& oth)const
{
return (Vec){x - oth.x, y - oth.y};
}
}H1, H2, L1, L2;
struct Node
{
db x; int flg;
bool operator < (const Node& oth)const
{
return x < oth.x;
}
}a[maxn];
int cnt = 0;
void solve(Point A, Point B, int flg)
{
Vec AB = B - A;
Vec CA = A - L1, CD = L2 - L1, DB = B - L2;
db s1 = CA * CD, s2 = -(DB * CD);
db ret = A.x + AB.x / (s1 + s2) * s1;
if(ret > L2.x) ret = L2.x; //限制N, M
if(ret < L1.x) ret = L1.x;
a[++cnt] = (Node){ret, flg};
}
int main()
{
while(scanf("%lf%lf%lf", &H1.x, &H2.x, &H1.y))
{
if(H1.x == 0 && H1.y == 0 && H2.x == 0) break;
cnt = 0;
H2.y = H1.y;
scanf("%lf%lf%lf", &L1.x, &L2.x, &L1.y); L2.y = L1.y;
n = read();
for(int i = 1; i <= n; ++i)
{
db L, R, y;
scanf("%lf%lf%lf", &L, &R, &y);
if(y < L1.y || y >= H1.y) continue;
solve(H1, (Point){R, y}, -1);
solve(H2, (Point){L, y}, 1);
}
if(!n) {printf("%.2f
", L2.x - L1.x); continue;}
sort(a + 1, a + cnt + 1);
a[cnt + 1].x = L2.x;
db ans = max(0.00, a[1].x - L1.x);
int st = 0; //模仿棧操作
for(int i = 1; i <= cnt; ++i)
{
st += a[i].flg;
if(!st) ans = max(ans, a[i + 1].x - a[i].x);
}
if(ans == 0) puts("No View");
else printf("%.2f
", ans);
}
return 0;
}