Codeforces Round #194 Div1E Summer Earnings

Codeforces

問題

N個の点の座標（整数）が与えられます。
この中から３点を選んで、その３点を中心として半径rの円を描きます。
このとき円は接してもいいけど交差しちゃダメです。
とりうるｒの最大値を求めなさい。

制約
(3 ≤ n ≤ 3000)
( - 10^4 ≤ xi, yi ≤ 10^4)


解法

３点を選んだ時のrの最大値は、（３点がつくる三角形の一番短い辺の長さ）/2　です。
というわけで、最短辺が最長になる三角形をこれらN個の点から求める問題になります。

editorialを見ると、△ABCの∠Bが60度以上（最小角ではない）とき、BCが最短辺とならないことを利用し、
１．Bを固定。
２．Bに対する角度で残りの点をソートし、60度以上の角度を持つ２点A,Cを選ぶ。選び方はセグメント木を使うのでO(nlogn)に抑えられる。

というようなことが書いてありました（若干怪しいというか、正直あんまりしっかり理解できてないですが…）。

しかし、もう少し愚直な方法を頑張っても通ってしまいました。というのも、
「全点間距離を計算し、距離が長い順に線を描いていき、三角形ができたら終了」
というものです。

最悪ケースは1500個ずつの２つのクラスタが出来ている場合で、1500*1500の辺を描いてもまだ三角形ができない場合があります。
「もう三角形ができているか」を判定するのにO(n)かかるとすると、この解法はO(n^3)なのですが、
この判定をbitsetを使って定数倍高速化するとなんと間に合ってしまいます。
（この問題のTime limitは9秒あり、最大ケースで3秒強かかっていました）


プログラム
いつものクセでx,yとかに無駄にlong longを使ったらMLEになる程度には制約厳しかったです。

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
#include<bitset>
using namespace std;


//#define int			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((int)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(int)n,sizeof(v))
#define bit(n)		(1ll<<(int)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define F first
#define S second
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

int x[3010], y[3010];
bitset<3030> ks[3030];
vector<pair<int, pair<int,int> > > v;

int len(int i, int j){
	return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}

int main(){
	int n;
	cin>>n;
	rin{ cin>>x[i]>>y[i]; }
	
	rep(i,n)rep(j,n)ks[i]=0;
	rep(i,n-1)repp(j,i+1,n)v.pb(mp(len(i,j), mp(i,j)));
	sort(allof(v));
	
	for(int i=sz(v)-1; i>=0; i--){
		int v1=v[i].S.F, v2=v[i].S.S;
		if((ks[v1]&ks[v2]).any()){
			printf("%.8f\n",sqrt((double)v[i].F/4.0));
			return 0;
		}
		ks[v2][v1]=ks[v1][v2]=true;
	}
	
	return 0;
}