Codechef-CIELMAP : Ciel and Map

問題概要

2次元平面上にN(<1000)個の点があり、このうち4点を選んで四角形を作りたい。このとき出てくる線分の中で考えられる最も長いものを求める問題。どの3点も同一直線上に無いことが保証されている。

解法

どの3点も同一直線上にないので、N=4以外のときは自由に選べる。N=4のときは単純に全探索すれば良い。多分純粋に全探索でも間に合うけどN=4のときの計算しやすさとTLE対策に一応凸法とってからやってみたら余裕だった。

acceptされたコード

#include <cmath>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

typedef double real;
const real PI = atan(1.0) * 4.0;
const real EPS = 1e-10;

struct Point{
	real x, y;
	Point();
	Point(double x, double y);
};

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

bool cmp_x(const Point& lhs, const Point& rhs){
	return lhs.x != rhs.x ? lhs.x < rhs.x : lhs.y < rhs.y;
}

bool cmp_y(const Point& lhs, const Point& rhs){
	return lhs.y != rhs.y ? lhs.y < rhs.y : lhs.x < rhs.x;
}

//デフォルトは辞書順比較にしておく
bool operator<(const Point& lhs, const Point& rhs){
	return cmp_x(lhs, rhs);
}

//演算子オーバーロード
//2項演算子
Point const operator+(const Point& lhs, const Point& rhs){
	return Point(lhs.x + rhs.x, lhs.y + rhs.y);
}

Point const operator-(const Point& lhs, const Point& rhs){
	return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

Point const operator*(const real lhs, const Point& rhs){
	return Point(lhs*rhs.x, lhs*rhs.y);
}

Point const operator*(const Point& lhs, const real rhs){
	return rhs * lhs;
}

Point const operator/(const Point& lhs, const real rhs){
	return Point(lhs.x/rhs, lhs.y/rhs);
}

//代入演算子
Point& operator+=(Point& lhs, const Point& rhs){
	lhs.x += rhs.x;
	lhs.y += rhs.y;
	return lhs;
}

Point& operator-=(Point& lhs, const Point& rhs){
	lhs.x -= rhs.x;
	lhs.y -= rhs.y;
	return lhs;
}

Point& operator*=(Point& lhs, const real rhs){
	lhs.x *= rhs;
	lhs.y *= rhs;
	return lhs;
}

Point& operator/=(Point& lhs, const real rhs){
	lhs.x /= rhs;
	lhs.y /= rhs;
	return lhs;
}

//単項演算子
Point const operator+(const Point& obj){
	return obj;
}

Point const operator-(const Point& obj){
	return Point(-obj.x, -obj.y);
}

ostream& operator<<(ostream& os, const Point& obj){
	return ( os << '(' << obj.x << ", " << obj.y << ')' );
}


real sq(real x){
	return x * x;
}

real abs2(const Point& p){
	return sq(p.x) + sq(p.y);
}

real abs(const Point& p){
	return sqrt(abs2(p));
}

real get_square_dist(const Point& lhs, const Point& rhs){
	return sq(lhs.x - rhs.x) + sq(lhs.y - rhs.y);
}

//2点間の距離を計算する
real get_dist(const Point& lhs, const Point& rhs){
	return sqrt(get_square_dist(lhs, rhs));
}

//内積を計算する
real iprod(const Point& lhs, const Point& rhs){
	return lhs.x * rhs.x + lhs.y * rhs.y;
}

//外積を計算する
real oprod(const Point& lhs, const Point& rhs){
	return lhs.x * rhs.y - lhs.y * rhs.x;
}

//行列式を計算する
real det(const Point& a, const Point& b, const Point& c){
	return oprod(a, b) + oprod(b, c) + oprod(c, a);
}

vector<Point> convex_hull(vector<Point> ps){
	sort(ps.begin(), ps.end(), cmp_x);
	const int n = ps.size();
	int k = 0;
	vector<Point> ret(n * 2);
	for(int i=0; i<n; ++i){
		for(;k>1 && oprod(ret[k-1] - ret[k-2], ps[i] - ret[k-1]) <= 0; k--);
		ret[k++] = ps[i];
	}
	for(int i=n-2, t=k; i>=0; i--){
		for(;k>t && oprod(ret[k-1] - ret[k-2], ps[i] - ret[k-1]) <= 0; k--);
		ret[k++] = ps[i];
	}
	ret.resize(k-1);
	return ret;
}

template<typename numType>
inline bool updateMax(numType& lhs, const numType& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return true;
	}
	return false;
}

int N;
vector<Point> ps;

void init() {
	scanf("%d", &N);
	ps.clear();
	ps.reserve(N);
	for (int i = 0; i < N; ++i) {
		int x, y;
		scanf("%d%d",&x, &y);
		ps.push_back(Point(x,y));
	}
}



double solve() {
	vector<Point> convexPoints = convex_hull(ps);
	double ans = 0.0;
	if (N == 4) {
		for (int i = 0; i < 4; ++i) {
			updateMax(ans, get_dist(convexPoints[i], convexPoints[(i+1)%4]));
		}
	}
	else {
		const int m = convexPoints.size();
		for (int i = 0; i < m; ++i) {
			for (int j = i + 1; j < m; ++j) {
				updateMax(ans, get_dist(convexPoints[i], convexPoints[j]));
			}
		}
	}

	return ans;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		init();
		printf("%.13f\n", solve());
	}
	return 0;
}