首页 > 代码库 > POJ 3301：Texas Trip（计算几何+三分）
POJ 3301：Texas Trip（计算几何+三分）
http://poj.org/problem?id=3301
题意：在二维平面上有n个点，每个点有一个坐标，问需要的正方形最小面积是多少可以覆盖所有的点。
思路：从第二个样例可以看出，将正方形旋转45°的时候，面积是最小的。
因此考虑旋转正方形，就可以当作旋转本来的点，对于旋转后的点，求最大的x和最小的x，最大的y和最小的y，就可以求得覆盖旋转后的点的正方形面积了。
然后对于每一个角度，都要进行判断，这个时候就觉得要用到X分了。
因为不满足单调性，所以用了三分。（其实也不太清楚为什么能三分）。
因为要求最小，因此是凹形的。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 using namespace std; 6 #define N 40 7 #define INF 0x3f3f3f3f 8 const double eps = 1e-9; 9 const double PI = acos(-1.0);10 struct node {11 double x, y;12 } p[N];13 int n;14 15 double cal(double ang) {16 double ix = 1000000000, iy = 1000000000, ax = -1000000000, ay = -1000000000;17 for(int i = 1; i <= n; i++) {18 double x = p[i].x * cos(ang) - p[i].y * sin(ang);19 double y = p[i].x * sin(ang) + p[i].y * cos(ang);20 ix = min(ix, x);21 iy = min(iy, y);22 ax = max(ax, x);23 ay = max(ay, y);24 }25 return max(ax - ix, ay - iy);26 }27 28 void Solve() {29 double l = 0, r = PI;30 while(fabs(r - l) > eps) {31 double mid = (l + r) / 2;32 double midd = (mid + r) / 2;33 if(cal(mid) <= cal(midd)) r = midd;34 else l = mid;35 }36 double ans = cal(l);37 printf("%.2f\n", ans * ans);38 }39 40 int main() {41 int t; scanf("%d", &t);42 while(t--) {43 scanf("%d", &n);44 for(int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);45 Solve();46 }47 return 0;48 }
POJ 3301：Texas Trip（计算几何+三分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。