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