POJ 1408:Fishnet
Time Limit:1000MS | Memory Limit:10000K | |
Total Submissions:1921 | Accepted:1234 |
Description
Input
Output
Sample Input
2 0.2000000 0.6000000 0.3000000 0.8000000 0.1000000 0.5000000 0.5000000 0.6000000 2 0.3333330 0.6666670 0.3333330 0.6666670 0.3333330 0.6666670 0.3333330 0.6666670 4 0.2000000 0.4000000 0.6000000 0.8000000 0.1000000 0.5000000 0.6000000 0.9000000 0.2000000 0.4000000 0.6000000 0.8000000 0.1000000 0.5000000 0.6000000 0.9000000 2 0.5138701 0.9476283 0.1717362 0.1757412 0.3086521 0.7022313 0.2264312 0.5345343 1 0.4000000 0.6000000 0.3000000 0.5000000 0
Sample Output
0.215657 0.111112 0.078923 0.279223 0.348958
题意是一张正方形的渔网,在上下左右四个边上都有n个点,上下边点对点对应连线,左右边点对点对应连线,然后这些连线会形成诸多四边形,问这些四边形中最大的面积是多少。
首先计算这些连线中间的交点,然后对每一个四边形求面积。求面积的方法是将四边形划成两个三角形,三角形的面积是用叉积/2来求。
代码:
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <iomanip> #pragma warning(disable:4996) using namespace std; struct node { double x, y; }point[35][35]; double xmult(node a, node b, node c) { return (a.x - c.x)*(b.y - c.y) - (b.x - c.x)*(a.y - c.y); } void init(int n) { point[0][0].x = 0.0; point[0][0].y = 0.0; point[0][n + 1].x = 1.0; point[0][n + 1].y = 0.0; point[n + 1][0].x = 0.0; point[n + 1][0].y = 1.0; point[n + 1][n + 1].x = 1.0; point[n + 1][n + 1].y = 1.0; } node intersection(node a,node b,node c,node d)//ab与cd直线的交点 { node temp = a; double t = ((a.x - c.x)*(c.y - d.y) - (a.y - c.y)*(c.x - d.x)) / ((a.x - b.x)*(c.y - d.y) - (a.y - b.y)*(c.x - d.x)); temp.x += (b.x - a.x)*t; temp.y += (b.y - a.y)*t; return temp; } int main() { int n, i, j; while (cin >> n) { if (!n) break; double maxn = 0.0, res; init(n); for (i = 1; i <= n; i++) { cin >> point[0][i].x; point[0][i].y = 0.0; } for (i = 1; i <= n; i++) { cin >> point[n + 1][i].x; point[n + 1][i].y = 1.0; } for (i = 1; i <= n; i++) { cin >> point[i][0].y; point[i][0].x = 0.0; } for (i = 1; i <= n; i++) { cin >> point[i][n + 1].y; point[i][n + 1].x = 1.0; } for (j = 1; j <= n; j++) { for (i = 1; i <= n ; i++) { point[i][j] = intersection(point[0][j], point[n + 1][j], point[i][0], point[i][n + 1]); } } for (i = 1; i <= n + 1; i++) { for (j = 1; j <= n + 1; j++) { res = fabs(xmult(point[i - 1][j - 1], point[i][j], point[i][j - 1])); res += fabs(xmult(point[i - 1][j - 1], point[i][j], point[i - 1][j])); res /= 2; maxn = max(res, maxn); } } cout << fixed << setprecision(6) << maxn << endl; } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。
优质内容筛选与推荐>>