ACAC002 C Diameter of a Convex Polygon

ここ数日幾何にハマっています。これはこの前本番で解けなかった問題。本番では全点間の距離の最大値で間に合うんじゃね？とか思って愚直な解法でやってTLEしてました(それでも22/24も通ったw)
久しぶりに問題を眺めてみると、コレこの前勉強したやつじゃんwとなったので解きました。

解法

キャリパー法で多角形をぐるんと回す。コレで勘弁してください。説明苦手です。わかりやすい解説は蟻本に載っています。

ソースコード

#include <cmath>
#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
#include <iomanip>
using namespace std;
#define eps 1e-9
#define pb push_back
double add(double a,double b)
{
	if(abs(a+b)<eps*(abs(a)+abs(b)))return 0;
	return a+b;
}
struct P
{
	double x,y;
	P (){}
	P(double x,double y):x(x),y(y){}
	P operator +(P p)
	{
		return P(add(x,p.x),add(y,p.y));
	}
	P operator -(P p)
	{
		return P(add(x,-p.x),add(y,-p.y));
	}
	P operator *(double d)
	{
		return P(x*d,y*d);
	}
	double dot(P p)
	{
		return add(x*p.x,y*p.y);
	}
	double det(P p)
	{
		return add(x*p.y,-y*p.x);
	}
};
bool comp(const P& p,const P& q)
{
	if(p.x!=q.x)return p.x<q.x;
	return p.y<q.y;
}
double dist(P p,P q)
{
	return sqrt((p-q).dot(p-q));
}
int main()
{
	vector<P> cv;
	int n;
	cin >> n;
	for(int i=0;i<n;i++)
	{
		P a;
		cin >> a.x >> a.y;
		cv.pb(a);
	}
	int i=0,j=0;
	for(int k=0;k<n;k++)
	{
		if(!comp(cv[i],cv[k]))i=k;
		if(comp(cv[j],cv[k]))j=k;
	}
	int si=i,sj=j;
	double ans=0;
	while(i!=sj||j!=si)
	{
		ans=max(ans,dist(cv[i],cv[j]));
		if((cv[(i+1)%n]-cv[i]).det(cv[(j+1)%n]-cv[j])<0)i=(i+1)%n;
		else j=(j+1)%n;
	}
	cout << setprecision(16) << ans << endl;
	return 0;
}