题意

就是求凸包点集的直径。

题解

当然选择旋转卡壳。

然后是实现上的技巧：

当Area(p[u], p[u+1], p[v+1]) <= Area(p[u], p[u+1], p[v])时停止旋转

即Cross(p[u+1]-p[u], p[v+1]-p[u]) - Cross(p[u+1]-p[u], p[v]-p[u]) <= 0

根据Cross(A,B) - Cross(A,C) = Cross(A,B-C)

化简得Cross(p[u+1]-p[u], p[v+1]-p[v]) <= 0

画个图就能发现，这样找的是对于一条边三角形的最大高。为什么这样是对的呢？

凸包上一个点到其他点的距离是一个凸函数。然后在两条直线慢慢旋转的过程中，可以考虑直接转一条边，这样求出的是到这条直线的最大距离，显然就是对踵点对。

实现的时候初始化可以直接暴力转，因为均摊是\(O(n)\)的。时间复杂度\(O(T n \log n)\)。

由于坐标都是整数，而又不涉及需要实数运算的操作，所以`Point`类可以直接实现为整数坐标。
```cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define rg register
#define il inline
#define co const
templateil T read()
{
rg T data=0;
rg int w=1;
rg char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
{
data=data*10+ch-'0';
ch=getchar();
}
return data*w;
}
templateT read(T&x)
{
return x=read();
}
using namespace std;
typedef long long ll;

struct Point

{

int x,y;

Point(int x=0,int y=0)

:x(x),y(y){}

bool operator<(co Point&rhs)co

{

	return x<rhs.x||(x==rhs.x&&y<rhs.y);

}

bool operator==(co Point&rhs)co

{

	return x==rhs.x&&y==rhs.y;

}

};

typedef Point Vector;

Vector operator-(co Point&A,co Point&B)

{

return Vector(A.x-B.x,A.y-B.y);

}

int Cross(co Vector&A,co Vector&B)

{

return A.xB.y-A.yB.x;

}

int Dot(co Vector&A,co Vector&B)

{

return A.xB.x+A.yB.y;

}

int Dist2(co Vector&A,co Vector&B)

{

return (A.x-B.x)(A.x-B.x)+(A.y-B.y)(A.y-B.y);

}

vectorConvexHull(vector&p)

{

sort(p.begin(),p.end());

p.erase(unique(p.begin(),p.end()),p.end());

int n=p.size();

int m=0;

vector<Point>ch(n+1);

for(int i=0;i<n;++i)

{

	while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)

		--m;

	ch[m++]=p[i];

}

int k=m;

for(int i=n-2;i>=0;--i)

{

	while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)

		--m;

	ch[m++]=p[i];

}

if(n>1)

	--m;

ch.resize(m);

return ch;

}

int Diameter2(vector&points)

{

vectorp=ConvexHull(points);

int n=p.size();

if(n1)

return 0;

if(n2)

return Dist2(p[0],p[1]);

p.push_back(p[0]); // avoid %

int ans=0;

for(int u=0,v=1;u<n;++u)

{

for(;

巴特西

LA4728 Squares

题意

题解

最新文章

热门文章