Nature|Nature Reserve CodeForces - 1059D(二分+精度)
传送门：QAQ
题意：给你n个动物的坐标，让你画个圆将所有的动物包括在内并且与y轴相切，问你是否存在这样的圆，并输出最小的圆半径。
【Nature|Nature Reserve CodeForces - 1059D(二分+精度)】
思路：很简单的二分形式，但是要怎么去检查这个半径是否可行呢。
因为这个圆是和y轴相切的，所以对于每个点我们都可以算出圆心的x轴范围，然后记录一下是否有共用范围就行了。
精度有点问题，突然发现浮点数运算的奥秘。
代码：
#include
#include
#include
#include
#include
using namespace std;
struct inst {
long double x;
long double y;
};
inst ax[110000];
long double mmm;
int n;
int check(long double x) {
if (ax[0].y < 0) x = -x;
long double l = -100000000000000000;
long double r = 100000000000000000;
for (int i = 0;
i < n;
i++) {
if (fabs(ax[i].y) > fabs(2 * x))
return 0;
long double ans = sqrt((ax[i].y)*((-ax[i].y)+(2*x)));
if (l < ax[i].x - ans)
l = ax[i].x - ans;
if (r > ax[i].x + ans)
r = ax[i].x + ans;
}
return l < r;
}
int main(void) {
scanf("%d", &n);
long double chm;
int fla = 0;
for (int i = 0;
i < n;
i++) {
scanf("%Lf%Lf", &ax[i].x, &ax[i].y);
if (i == 0) {
chm = ax[i].y;
if (chm == 0) fla = 1;
}
chm = ax[i].y*ax[0].y;
if (chm <= 0) fla = 1;
}
if (fla) {
printf("-1\n");
return 0;
}
long double le = 0;
long double ri = 1000000000000000;
for(int i=1;
i<=100;
i++){
long double mid = (le + ri)/2;
if (check(mid)) {
ri = mid;
}
else {
le = mid;
}
//printf("%lf %lf %lf\n", mid,le,ri);
}
printf("%Lf\n", ri);
} 推荐阅读
- Java接口签名(Signature)实现方案
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence
- Codeforces580|Codeforces580 D. Kefa and Dishes（状压dp）
- Codeforces22|Codeforces22 D. Segments（贪心）
- codeforces|codeforces 667C C. Reberland Linguistics(dp)