ZOJ3413 Special Special Judge III(数形结合)

青旅半醒 2022-06-11 04:51 121阅读 0赞

Special Special Judge III

--------------------

Time Limit: 2 Seconds       Memory Limit: 65536 KB

--------------------

Because of recent update of ZOJ, some special judges were broken. You're requested to fix the special judge for Problem 9999.

In Problem 9999, there is only one case in where the standard output is two real number *x* and *y*. The special judge uses two parameters: one is the sum of the two numbers in standard output (*x* and *y*); the other is the sum of the two numbers in the output of submitted solution (*p* and *q*). If the absolute value of the difference of these two parameters does not exceed *k*, the submitted solution will be accepted.

Knowing that the range of *p* is \[0, *a*\] and the range of *q* is \[0, *b*\]. What's the possibility that a solution outputting *p* and *q* with equal probability will get accepted.

**Input**

There are no more than 10000 test cases. You should process to the end of input. For each test case, there are only one line with 5 real numbers *x*, *y*, *a*, *b*, *k*, (0 <= *x* <= 1000, 0 <= *y* <= 1000, 0 <= *a* <= 1000, 0 <= *b* <= 1000, 0 <= *k* <= 1000).

**Output**

For each case, you should print out a single line indicating the possibility of getting accepted using the random solution. Your answer is supposed to be rounded to six decimal digits.

**Sample Input**

2 2 4 4 4
    2 2 2 2 1

**Sample Output**

1.000000
    0.125000

题意：给你两个标准答案x,y，再给你两个范围a,b，和一个误差k，系统每次会随机输出两个数字p,q且满足0<=p<=a,0<=q<=b，若x+y与p+q的差值不超过k，则此次答案可以AC，求AC的概率，保留小数点后六位。

思路：这道题我们可以转化为一道计算几何的题目

如图所示，因为0<=p<=a,0<=q<=b，所以红色部分就是随机给出的答案，而正确答案则是深蓝色的那条线，因为误差为k，所以那条线±k的两条线，也就是图中两条浅蓝色的线，它们之间的部分都可以算作正确答案，那么答案就显而易见了，AC率就是绿色部分的面积/(a*b)。接下来我们就要对浅蓝色的线进行分类讨论。

蓝色的线有两条，对于一条线可能有五种情况：

①，与红色矩形完全不相交，并在其下方。

②，与红色矩形左边和下边相交。

③，与红色矩形上边和下边相交。

④，与红色矩形上边和右边相交。

⑤，与红色矩形完全不相交，并在其上方。

那么对于两条线来说就有以下15种搭配

1，①①  2，①②  3，①③  4，①④  5，①⑤

6，②②  7，②③  8，②④  9，②⑤  10，③③

11，③④ 12，③⑤ 13，④④ 14，④⑤ 15，⑤⑤

每一种情况对应的绿色部分的面积都可以轻松求出来，答案自然也就出来了。

但是这题还有很多坑，首先就是当a,b为0的情况，如果a=0,b!=0或者b=0,a!=0，那么我们的红色矩形明显就变成了一条线，这个时候就不能用面积去除了，我们要用浅蓝色的线把红色线所截的长度除以红线原来的长度，这才是正确答案，如果a=0&&b=0，那红色部分就变成了一个点，这个时候只要特判一下绿色部分有没有包含原点就行了，如果包含了答案就是1，没有包含就是0。考虑完a，b为0的情况再考虑k为0的情况，如果k为0，那么两条浅蓝色的线就和深蓝色的线重叠成一条线，这个时候除非红色部分刚好是个点并且过这条线，否则答案只会是0，因为我们之前已经判断过红色部分是个点的情况了，所以这里可以直接默认如果k=0则答案是0。最后一个坑点就是关于double的精度问题，我当时这道题就是因为精度问题WA了好多发，在比赛时没做出来，在这里我给大家推荐一个专门讲解精度问题的博客，传送门→http://www.cnblogs.com/crazyacking/p/4668471.html

然后这道题就可以A了，下面是AC代码

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 1000005;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1; }//解决精度问题的函数
    
    int main()
    {
    	double x, y, a, b, k;
    	double t;
    	double pmax, pmin;
    	double s;
    	while (scanf("%lf%lf%lf%lf%lf", &x, &y, &a, &b, &k) != EOF)
    	{
    		s = 0;
    		if (sgn(a - b) < 0)
    		{
    			t = a;
    			a = b;
    			b = t;
    		}
    		pmax = x + y + k;
    		pmin = x + y - k;
    		if (sgn(a - 0) == 0 || sgn(b - 0) == 0)
    		{
    			if (sgn(a - 0) == 0 && sgn(b - 0) != 0)
    			{
    				s = (min(pmax, b) - max(0.0, pmin)) / b;
    				printf("%.6lf\n", s);
    				continue;
    			}
    			if (sgn(b - 0) == 0 && sgn(a - 0) != 0)
    			{
    				s = (min(pmax, a) - max(0.0, pmin)) / a;
    				printf("%.6lf\n", s);
    				continue;
    			}
    			if (sgn(a - 0) == 0 && sgn(b - 0) == 0)
    			{
    				if (sgn(pmax - 0) >= 0 && sgn(pmin - 0) <= 0)
    					printf("1.000000\n");
    				else
    					printf("0.000000\n");
    				continue;
    			}
    		}
    		if (sgn(pmax - pmin) == 0)
    		{
    			printf("0.000000\n");
    			continue;
    		}
    		if (sgn(pmin - 0) <= 0 && sgn(pmax - 0) <= 0)
    			s = 0;
    		else if (sgn(pmin - 0) <= 0 && sgn(pmax - 0) >= 0 && sgn(pmax - b) <= 0 && sgn(pmin - b) <= 0)
    			s = pmax*pmax / 2.0;
    		else if (sgn(pmin - 0) >= 0 && sgn(pmin - b) <= 0 && sgn(pmax - 0) >= 0 && sgn(pmax - b) <= 0)
    			s = pmax*pmax / 2.0 - pmin*pmin / 2.0;
    		else if (sgn(pmin - 0) >= 0 && sgn(pmin - b) <= 0 && sgn(pmax - b) >= 0 && sgn(pmax - a) <= 0)
    			s = (2 * pmax - b)*b / 2.0 - pmin*pmin / 2.0;
    		else if (sgn(b - pmin) <= 0 && sgn(pmin - a) <= 0 && sgn(b - pmax) <= 0 && sgn(pmax - a) <= 0)
    			s = (pmax - pmin)*b;
    		else if (sgn(b - pmin) <= 0 && sgn(pmin - a) <= 0 && sgn(pmax - a) >= 0 && sgn(pmax - (b+a)) <= 0)
    			s = (2 * (a - pmin) + b)*b / 2.0 - (a - pmax + b)*(a - pmax + b) / 2.0;
    		else if (sgn(pmin - a) >= 0 && sgn(pmin - (a+b)) <= 0 && sgn(pmax - a) >= 0 && sgn(pmax - (a+b)) <= 0)
    			s = (a - pmin + b)*(a - pmin + b) / 2.0 - (a - pmax + b)*(a - pmax + b) / 2.0;
    		else if (sgn(pmin - a) >= 0 && sgn(pmin - (a+b)) <= 0 && sgn(pmax - (a+b)) >= 0)
    			s = (a - pmin + b)*(a - pmin + b) / 2.0;
    		else if (sgn(pmax - (a+b)) >= 0 && sgn(pmin - (a+b)) >= 0)
    			s = 0;
    		else if (sgn(pmin - 0) >= 0 && sgn(pmin - b) <= 0 && sgn(pmax - a) >= 0 && sgn(pmax - (a+b)) <= 0)
    			s = a*b - pmin*pmin / 2.0 - (a - pmax + b)*(a - pmax + b) / 2.0;
    		else if (sgn(pmin - 0) <= 0 && sgn(pmax - b) >= 0 && sgn(pmax - a) <= 0)
    			s = (2 * pmax - b)*b / 2.0;
    		else if (sgn(pmin - 0) <= 0 && sgn(pmax - a) >= 0 && sgn(pmax - (a+b)) <= 0)
    			s = a*b - (a - pmax + b)*(a - pmax + b) / 2.0;
    		else if (sgn(pmin - 0) <= 0 && sgn(pmax - (a+b)) >= 0)
    			s = a*b;
    		else if (sgn(pmin - 0) >= 0 && sgn(pmin - b) <= 0 && sgn(pmax - (a+b)) >= 0)
    			s = a*b - pmin*pmin / 2.0;
    		else if (sgn(pmin - a) <= 0&& sgn(pmin - b) >= 0 && sgn(pmax - (a+b)) >= 0)
    			s = a*b - (2 * pmin - b)*b / 2.0;
    		else
    			s = 0;
    		printf("%.6lf\n", s / (a*b));
    	}
    }