poj 3334 Connected Gheeves (Geometry + BInary Search)
2024-10-08 02:58:34
题意是,给出两个尖形的相连的容器,要求向其中灌水。它们具有日常的物理属性,例如两个容器中水平面高度相同以及水高于容器顶部的时候就会溢出。开始的时候打算直接用几何的计算,求出精确值。后来发现,这样的计算实在是太麻烦了,实现起来有很多细节要注意。于是,后来就想到了用二分的方法,枚举水平面的高度,然后求直线切割容器得到的多边形的面积,因为这个面积会随着水平面的高度具有单调性。注意预先确定好二分的上下界即可。1y~
代码如下:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath> using namespace std; const double EPS = 1e-;
const double FINF = 1e10;
const int N = ;
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
bool operator < (Point a) const { return sgn(x - a.x) < || sgn(x - a.x) == && sgn(y - a.y) < ;}
bool operator == (Point a) const { return sgn(x - a.x) == && sgn(y - a.x) == ;}
} ;
typedef Point Vec;
Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);} template<class T> T sqr(T x) { return x * x;}
inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);} double polyArea(Point *pt, int n) {
double ret = 0.0;
pt[n] = pt[];
for (int i = ; i < n; i++) ret += crossDet(Point(0.0, 0.0), pt[i], pt[i + ]);
return fabs(ret) / 2.0;
}
inline Point lineIntersect(Point P, Vec u, Point Q, Vec v) { return P + u * (crossDet(v, P - Q) / crossDet(u, v));} Point gheef[][N], tmp[N];
double bottom[];
int n[]; double getArea(double x, int id) {
if (x <= bottom[id]) return 0.0;
Point s = Point(-FINF, x), t = Point(FINF, x);
for (int i = ; i < n[id]; i++) tmp[i] = gheef[id][i];
int l = , r = n[id] - ;
while (crossDet(tmp[l], s, t) * crossDet(tmp[l + ], s, t) > ) l++;
while (crossDet(tmp[r], s, t) * crossDet(tmp[r - ], s, t) > ) r--;
tmp[l] = lineIntersect(s, t - s, tmp[l], tmp[l + ] - tmp[l]);
tmp[r] = lineIntersect(s, t - s, tmp[r], tmp[r - ] - tmp[r]);
return polyArea(tmp + l, r - l + );
} double getArea(double x) {
double ret = 0.0;
for (int i = ; i < ; i++) {
ret += getArea(x, i);
}
return ret;
} double dc2(double x) {
// cout << getArea(3.536) << endl;
double l = min(bottom[], bottom[]), r = min(min(gheef[][].y, gheef[][].y), min(gheef[][n[] - ].y, gheef[][n[] - ].y));
// cout << l << " l r " << r << endl;
while (l + 1e- < r) {
double m = (l + r) / 2.0;
if (getArea(m) > x) r = m;
else l = m;
}
return l;
} int main() {
// freopen("in", "r", stdin);
int T;
double v;
cin >> T;
while (T-- && cin >> v) {
for (int i = ; i < ; i++) {
cin >> n[i];
bottom[i] = FINF;
for (int j = ; j < n[i]; j++) {
cin >> gheef[i][j].x >> gheef[i][j].y;
bottom[i] = min(bottom[i], gheef[i][j].y);
}
}
printf("%.3f\n", dc2(v));
}
return ;
}
——written by Lyon
最新文章
- Linux非root用户如何使用80端口启动程序
- 在windows下配置wnmp
- 冲刺阶段day7
- c语言类型转换注意事项
- Java读写大文本文件(2GB以上)
- 免费的天气Web Service接口
- UOJ 08 Quine 是在下输了
- IIS服务器应用程序不可用的解决办法
- jQuery.ajax()的一些例子
- Github开源Java项目(Disconf)上传到Maven Central Repository方法详细介绍
- LibSvm介绍---调用方法及参数介绍
- 迈向angularjs2系列(6):路由机制
- encodeURIComponent() 函数
- Shell与脚本
- DI是实现面向切面和面向抽象的前提
- opencv学习记录
- Android仿淘宝头条滚动广告条
- PAT 甲级 1086 Tree Traversals Again
- Python爬虫教程-08-post介绍(百度翻译)(下)
- oracle goldengate的两种用法
热门文章
- Swift 和 Objective-C 混编后对ipa包大小的影响
- python之特点
- Javascript-正则表达式常用字符集及方法
- 模拟20 题解(waiting)
- Codeforces 375A
- setStorage、getStorage、 removeStorage 封装
- windows上安装Anaconda和python的教程详解
- docker.[6] 数据卷
- 第一周<;单元一聚类>;
- git pull 提示错误,Your local changes to the following files would be overwritten by merge