首页 > 代码库 > LA 2402 (枚举) Fishnet
LA 2402 (枚举) Fishnet
题意：
正方形四个边界上分别有n个点，将其划分为(n+1)2个四边形，求四边形面积的最大值。
分析：
因为n的规模很小，所以可以二重循环枚举求最大值。
求直线(a, 0) (b, 0) 和直线(0, c) (0, d)的交点，我是二元方程组求解得来的，然后再用叉积求面积即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 6 const int maxn = 30 + 10; 7 struct HEHE 8 { 9 double a, b, c, d;10 }hehe[maxn];11 12 struct Point13 {14 double x, y;15 Point(double x=0, double y=0):x(x), y(y) {}16 };17 typedef Point Vector;18 19 Vector operator - (const Vector& A, const Vector& B)20 { return Vector(A.x - B.x, A.y - B.y); }21 22 double Cross(const Vector& A, const Vector& B)23 { return (A.x*B.y - A.y*B.x); }24 25 Point GetIntersection(const double& a, const double& b, const double& c, const double& d)26 {27 double x = (a+(b-a)*c) / (1-(b-a)*(d-c));28 double y = (d-c)*x+c;29 return Point(x, y);30 }31 32 int main(void)33 {34 //freopen("2402in.txt", "r", stdin);35 36 int n;37 while(scanf("%d", &n) == 1 && n)38 {39 memset(hehe, 0, sizeof(hehe));40 for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].a);41 for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].b);42 for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].c);43 for(int i = 1; i <= n; ++i) scanf("%lf", &hehe[i].d);44 hehe[n+1].a = hehe[n+1].b = hehe[n+1].c = hehe[n+1].d = 1.0;45 46 double ans = 0.0;47 for(int i = 0; i <= n; ++i)48 for(int j = 0; j <= n; ++j)49 {50 Point A, B, C, D;51 A = GetIntersection(hehe[i].a, hehe[i].b, hehe[j].c, hehe[j].d);52 B = GetIntersection(hehe[i+1].a, hehe[i+1].b, hehe[j].c, hehe[j].d);53 C = GetIntersection(hehe[i+1].a, hehe[i+1].b, hehe[j+1].c, hehe[j+1].d);54 D = GetIntersection(hehe[i].a, hehe[i].b, hehe[j+1].c, hehe[j+1].d);55 double temp = 0.0;56 temp += Cross(B-A, C-A) / 2;57 temp += Cross(C-A, D-A) / 2;58 ans = std::max(ans, temp);59 }60 61 printf("%.6f\n", ans);62 }63 64 return 0;65 }
LA 2402 (枚举) Fishnet
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。