NYOJ952--最大四边形--叉积分成三角形

NYOJ952--最大四边形--叉积分成三角形

最大四边形

链接：​​click here​​

时间限制：1000 ms  |  内存限制：65535

难度：2

描述 平面坐标上有n个点，你知道能组成四边形中面积最大的是多少吗？ 输入 有多组测试数据

第一行整数n，表示有n个点，( 4<=n<=300 )

然后n行，每行x，y表示点的坐标。(没有重复的点)

输出 最大四边形的面积.(保留六位小数) 样例输入

50 00 44 04 42 3

样例输出

16.000000

模板题;

/*************Times:236msNYOJ 952***************/#include#include#include#include#include#include#include#includeusing namespace std;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{0,-1},{-1,0},{0,1},{1,0}};const double Pi = acos(-1.0);const int maxn=500;const double eps=1e-10;struct point{ double x,y; point(double xx=0,double yy=0):x(xx),y(yy) {}//构造函数} p[maxn];typedef point PP;PP operator - (PP a,PP b){ return PP(a.x-b.x,a.y-b.y);}double cross (PP a,PP b){ return (a.x*b.y-a.y*b.x)*0.5;}int main(){ //freopen("1.txt","r",stdin); int n,i,j,k; while(cin>>n) { for(i=0; i/**************Times:116ms;**************/#include #include #include #include #include #include using namespace std;#define LL long longconst int N = 305;const double eps = 1e-8;struct POINT{ double x, y;}p[N];int n;double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);}double Area(POINT a, POINT b){ double lmax = 0, rmax = 0; for(int i = 0; i < n; i ++){ double tmp = cross(a, b, p[i]); if(tmp < eps) lmax = max(lmax, -tmp); if(tmp > eps) rmax = max(rmax, tmp); } if(lmax == 0 || rmax == 0) return 0; return (lmax + rmax) / 2.0;}int main(){// freopen("input.txt", "r", stdin); while(~scanf("%d", &n)){ for(int i = 0; i < n; i ++){ scanf("%lf %lf", &p[i].x, &p[i].y); } double ans = 0; for(int i = 0; i < n; i ++){ for(int j = i + 1; j < n; j ++) ans = max(ans, Area(p[i], p[j])); } printf("%.6lf\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。