ZOJ Monthly, October 2010解题报告 » ZOJ3413

ZOJ3413
ZOJ3413.cpp


#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

//?????
//???????
const int MAXN = 100;
const double EPS = 1e-8;

struct Point {
	double x, y;
	Point() { }
	Point(double x, double y) : x(x), y(y) { }
};

inline bool zero(double x) {
	return ((x > 0 ? x : -x) < EPS);
}

inline double xmult(const Point & p1, const Point & p2, const Point & p0) {
	return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

bool sameSide(const Point & p1, const Point & p2, const Point & l1, const Point & l2) {
	return xmult(l1, p1, l2) * xmult(l1, p2, l2) > EPS;
}

Point intersection(const Point & u1, const Point & u2, const Point & v1, const Point & v2) {
	Point ret = u1;
	double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) / ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
	ret.x += (u2.x - u1.x) * t;
	ret.y += (u2.y - u1.y) * t;
	return ret;
}

//?????l1, l2????????side???, ??l1, l2, side???
void polygonCut(int & n, Point * p, const Point & l1, const Point & l2, const Point & side) {
	Point pp[MAXN];
	int m = 0, i;
	for (i = 0; i < n; i++) {
		if (sameSide(p[i], side, l1, l2)) {
			pp[m++] = p[i];
		}
		if (!sameSide(p[i], p[(i + 1) % n], l1, l2) && !(zero(xmult(p[i], l1, l2)) && zero(xmult(p[(i + 1) %n ], l1, l2)))) {
			pp[m++] = intersection(p[i], p[(i + 1) % n], l1, l2);
		}
	}
	for (n = i = 0; i < m; i++) {
		if (!i || !zero(pp[i].x - pp[i - 1].x) || !zero(pp[i].y - pp[i-1].y)) {
			p[n++] = pp[i];
		}
	}
	if (zero(p[n - 1].x - p[0].x) && zero(p[n - 1].y - p[0].y)) {
		n--;
	}
	if (n < 3) {
		n = 0;
	}
}

double areaPolygon(int n, const Point* p) {
	double s1 = 0, s2 = 0;
	for (int i = 0; i < n; i++) {
		s1 += p[(i + 1) % n].y * p[i].x;
		s2 += p[(i + 1) % n].y * p[(i + 2) % n].x;
	}
	return fabs(s1 - s2)/2;
}

int main() {
	double x, y, a, b, k, l, r, ans;
	Point p[100], u, v;
	int n;

	while (scanf("%lf%lf%lf%lf%lf", &x, &y, &a, &b, &k) != EOF) {
		if (a == 0 && b == 0) {
			ans = (x + y <= k + 1e-8 ? 1 : 0);
		} else if (a == 0) {
			l = max(0.0, x + y - k);
			r = min(b, x + y + k);
			ans = (l < r ? r - l : 0.0);
			ans /= b;
		} else if (b == 0) {
			l = max(0.0, x + y - k);
			r = min(a, x + y + k);
			ans = (l < r ? r - l : 0.0);
			ans /= a;
		} else {
			n = 4;
			p[0] = Point(0, 0);
			p[1] = Point(a, 0);
			p[2] = Point(a, b);
			p[3] = Point(0, b);
			polygonCut(n, p, Point(x + y - k, 0), Point(x + y - k + 100, -100), Point(2000, 2000));
			polygonCut(n, p, Point(x + y + k, 0), Point(x + y + k + 100, -100), Point(-2000, -2000));
			ans = areaPolygon(n, p) / a / b;
		}
		printf("%.6lf\n", fabs(max(0.0, min(1.0, ans))));
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//321 	2010-10-05 22:27:44 	Accepted 	H 	C++ 	70 	180 	watashi@Zodiac 	Source
4 Responses to “ZOJ3413”
  1. Krh says:

    非常感谢!随便膜拜一下!

  2. Krh says:

    这位神牛,看了上面代码,我发觉这组数据很奇怪
    0.000007 0.000013 0.000013 0.000008 0.000005
    0.0000007 0.0000013 0.0000013 0.0000008 0.0000005
    0.00000007 0.00000013 0.00000013 0.00000008 0.00000005
    我的程序结果都一样的。麻烦帮忙看一下,谢谢。

    • watashi says:

      我用python版http://watashi.ws/blog/1515/zojmonthly1010/zoj3413p/跑的结果也都是一样的:
      0.173077
      0.173077
      0.173077
      C++版本之所以不一样是因为EPS的缘故,所以解题报告里说了这个方法不推荐。

    • watashi says:

      我看了你email给我的程序,跑了一下数据,似乎只有一个bug,就是你会输出”-0.000000″
      patpat

  3.  
Leave a Reply