| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
第100道,贴份代码#include <cstdio>
#include <cmath>
#include <list>
using namespace std;
const double eps = 1e-8;
inline bool iszero(double x) {
return fabs(x) < eps;
}
struct Interval {
double x1, x2;
Interval() {}
Interval(double x1, double x2) : x1(x1), x2(x2) {}
double size() { return x2 - x1; }
};
double solve(double x1, double y1, double x2, double y2, double y3) {
return x2 + (x2 - x1) * (y3 - y2) / (y2 - y1);
}
double hx1, hx2, hy;
double px1, px2, py;
Interval shadow(double obx1, double obx2, double oby) {
double x1 = solve(hx2, hy, obx1, oby, py);
double x2 = solve(hx1, hy, obx2, oby, py);
return Interval(x1, x2);
}
#define le(x, y) ((x) < (y) || iszero((x) - (y)))
#define ge(x, y) ((x) > (y) || iszero((x) - (y)))
int gettype(Interval& intv1, Interval& intv2) {
if (le(intv1.x2, intv2.x1) || ge(intv1.x1, intv2.x2)) return 0;
if (intv1.x1 < intv2.x1
&& intv1.x2 > intv2.x1 && intv1.x2 < intv2.x2) return 1;
if (intv2.x1 < intv1.x1
&& intv2.x2 > intv1.x1 && intv2.x2 < intv1.x2) return 2;
if (ge(intv1.x1, intv2.x1) && le(intv1.x2, intv2.x2)) return 3;
if (ge(intv2.x1, intv1.x1) && le(intv2.x2, intv1.x2)) return 4;
}
int main() {
int n, i;
while (scanf("%lf%lf%lf", &hx1, &hx2, &hy) != EOF) {
if (iszero(hx1) && iszero(hx2) && iszero(hy)) break;
scanf("%lf%lf%lf", &px1, &px2, &py);
scanf("%d", &n);
list<Interval> L;
list<Interval>::iterator iter1, iter2;
L.push_back(Interval(px1, px2));
for (i = 0; i < n; i++) {
double obx1, obx2, oby;
scanf("%lf%lf%lf", &obx1, &obx2, &oby);
if (oby < hy && ge(oby, py)) {
Interval intv = shadow(obx1, obx2, oby);
for (iter1 = L.begin(); iter1 != L.end(); iter1 = iter2) {
iter2 = ++iter1; iter1--;
int type = gettype(intv, *iter1);
if (type == 1) iter1->x1 = intv.x2;
else if (type == 2) iter1->x2 = intv.x1;
else if (type == 3) {
L.insert(iter1, Interval(iter1->x1, intv.x1));
iter1->x1 = intv.x2;
} else if (type == 4) L.erase(iter1);
}
}
}
double max = 0.0;
for (iter1 = L.begin(); iter1 != L.end(); iter1++) {
if (iter1->size() > max) max = iter1->size();
}
if (iszero(max)) printf("No View\n");
else printf("%.2lf\n", max);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator