Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第100道,贴份代码

Posted by bestofme at 2014-05-05 00:49:26 on Problem 2074
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator