三分题解

为啥要写这么简单题的题解呢？因为让我想起了团队里的一道题，直到今天我才知道那道题的做法

废话不多说，我们可以发现，要求的就是最远的距离，我们把玻璃看成旋转橡皮擦，或者是说我们可以通过旋转比较在每一个方向上两两的距离来找他的直径（）

那么我旋转180度，只会有一个点是最大的，并且这个是一个单调的过程（我也不知道怎么证明，玩两下就知道了）

那么我们就可以写一个三分，代码如下：

#include <cstdio>
#include <cmath>

const double pi=acos(-1.0);

using namespace std;

int n,m;

double a[1000010],b[1000010];

double h(double x)
{
  double max1,max2,maxn=0;
  for(int i=1;i<=m;i++)
  {
    for(int j=i+1;j<=m;j++)
    {
      max1=fabs((a[i]-a[j])*sin(x)-(b[i]-b[j])*cos(x));
      max2=fabs((a[i]-a[j])*cos(x)+(b[i]-b[j])*sin(x));
      if(max1>maxn) maxn=max1;
      if(max2>maxn) maxn=max2;
    }
  }
  return maxn;
}

int main()
{
  scanf("%d",&n);
  while(n--)
  {
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
      scanf("%lf%lf",&a[i],&b[i]);
    }
    double l=0.0,r=pi;
    while(r-l>1e-9)
    {
      double mid=(l+r)/2;
      double rmid=(mid+r)/2;
      if(h(mid)>h(rmid)) l=mid;
      else r=rmid;
    }
    double ans=h(l);
    printf("%.2f
",ans*ans);
  }
}

至于团队中的题，也许是这个的加强版吧