Codeforces Round #198 (Div. 2) —— B

时间:2023-12-17 08:13:56

B题是一个计算几何的题,虽然以前看过计算几何的ppt,但一直都没有写过;

昨晚比赛的时候本来想写的,但是怕不熟练浪费时间,太可惜了!

其实没必要选出一个最大的矩形;

以矩形的一条对角线为轴,向上或者向下找到最大的三角形的面积就行了,

可以看看官方的题解,讲的挺不错的!

代码:

 #include<cstdio>
#define eps 0.00000001
using namespace std;
int a[][];
double ccw(int x,int y,int z)
{
return ((double)(a[y][]-a[x][])*(a[z][]-a[x][])-(a[y][]-a[x][])*(a[z][]-a[x][]))*0.5;
}
double check(double x,double y)
{
if(y-x>=eps)
return y;
else return x;
}
int main()
{
int n;
double ans=;
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d%d",&a[i][],&a[i][]);
for(int i=;i<n;i++)
for(int j=i+;j<n;j++)
{
double min=-,max=-;
for(int k=;k<n;k++)
if(k!=i&&k!=j)
{
if(ccw(i,j,k)<)
min=check(min,-ccw(i,j,k));
else
max=check(max,ccw(i,j,k));
}
if(max>=&&min>=)
ans=check(ans,max+min);
}
printf("%lf\n",ans);
return ;
}