PKU演習問メモ(6/28)

立ち直れない。おまけに風邪っぽい。

No.	問題名	問題の種類および解法	難易度
2187	Beauty Contest	幾何（最遠二点間距離）	★★★☆☆

2187 Beauty Contest

問題概要

n(n≤50000)個の点が与えられる。これらのうちで最も遠い二点間の距離を求めよ。

解法

n個の点を全て試すとおそらくTLE.
n個の点の凸包を取りO(nlog n)、凸多角形の最遠頂点対間距離をO(n)で求めるキャリパー法を用れば全体でO(nlog n)で解ける。
上位は一桁〜二桁速いのでもっと効率の良い解法があるのかも。

ソースコード

Spaghetti sourceのコードを使用。（リンク参照）

int main()
{
  int n; scanf("%d",&n);
  vector<P> pt;
  rep(i,n){
    int x,y; cin>>x>>y;
    pt.pb(P(x,y));
  }
  vector<P> ch=convex_hull(pt);
  cout<<convex_diameter(ch)<<endl;
  return 0;
}