nyoj952最大四边形 思路+代码

5
0 0
0 4
4 0
4 4
2 3

16.000000

TC_常红立

思路：

这道题目技巧很巧妙，利用了叉乘的性质。首先任取两个点作为分界线，在分界线两边分别取两个点与分界线组成有一条公共边的两个三角形，枚举所有可能性，求出两个三角形的和最大即为最大四边形面积。求Sabc=ac×ab*0.5（叉乘意义）。

#include<bits/stdc++.h>
using namespace std;
struct point
{double x,y;
}p[305],s[305];
int cmp(point a,point b)
{if(a.x==b.x)return a.y<b.y;else  return a.x<b.x;
}
double maxx(double a,double b)
{if(a>=b) return a;else return b;
}double judge2(point a, point b, point c)//ab×ac叉乘
{double bax = b.x-a.x;double bay = b.y-a.y;double cax = c.x-a.x;double cay = c.y-a.y;return (bax*cay - bay*cax )*0.5;
}
int main()
{int n;while(~scanf("%d",&n)){memset(s,0,sizeof(s));memset(p,0,sizeof(p));for(int i=0;i<n;i++)scanf("%lf %lf",&p[i].x,&p[i].y);double s1=0,s2=0,S=0;double sm1=0,sm2=0;double flag;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(j==i) continue;s1=0,s2=0;for(int k=0;k<n;k++){if(k!=i&&k!=j)//分界线为ij{flag=judge2(p[k],p[i],p[j]);// cout<<flag<<endl;if(flag>=0)//通过叉乘正负来判断点在分界线那边{sm1=fabs(flag);//  cout<<sm1<<endl;if(s1<sm1) s1=sm1;}else{sm2=fabs(flag);//cout<<sm2<<endl;if(s2<sm2) s2=sm2;}// cout<<s1<<" "<<s2<<endl;// cout<<k<<" "<<i<<" "<<j<<endl;}}if(s1&&s2)S=maxx(S,s1+s2) ;//对每一条分界线求出最大面积然后对比直到求出遍历所有点的最大四边形面积}}//cout<<s1<<" "<<s2<<endl;//S=s1+s2;printf("%.6lf\n",S);}return 0;
}