Codeforces Round #352 (Div. 2) C. Recycling Bottles

問題

Problem - C - Codeforces
2人の人間、リサイクル箱、N個のボトルが平面空間に置かれている。
それぞれの人間は、ボトルを1つ拾いに行き、リサイクル箱に入れるという行動を任意の回数繰り返す(0でもよい)。
2人の移動距離の総和の最小値を出力せよ。

解法

最初に取る行動として、
(最後まで)何もしない,1番目のボトルを拾いに行く, ... ,N番目のボトルを拾いに行く
の中から2人が被らないように選ぶと、残りはどちらの人がリサイクル箱との往復をしまくればよい。
最初の行動でなるべく移動距離を減らしたいので、最初の行動は、その行動によって減らせる移動距離の大きいものを選ぶべき。
ただしそれぞれの人にとっての最適が被る場合もあるので、それぞれの人について有益度上位2つまでの行動を試す(全部で4通り)。

実装

double型のINFの値はでかくするべき(戒め)
最初は2人の最適な行動が被る場合を場合分けしていたけど、全部の場合を2*2のループで包み込んでしまう実装に(言われて)変えたらすっきりした。
あとcodeforcesやたらcin重くない

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_N = 100000;
const double DINF = 1e19;

struct Point
{
	double x, y;
	Point() {}
	Point(double _x, double _y)
	{
		x = _x; y = _y;
	}
	double abs() const
	{
		return sqrt(x*x + y*y);
	}
	double GetDist(const Point &p) const
	{
		return Point(x - p.x, y - p.y).abs();
	}
};

Point a, b, t, p[MAX_N];
int N;
pair<double, int> da[MAX_N + 1], db[MAX_N + 1];

signed main()
{
	cin >> a.x >> a.y >> b.x >> b.y >> t.x >> t.y >> N;
	double sum = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%lf%lf", &p[i].x, &p[i].y);
		sum += t.GetDist(p[i]);
		da[i] = make_pair(t.GetDist(p[i]) - a.GetDist(p[i]), i);
		db[i] = make_pair(t.GetDist(p[i]) - b.GetDist(p[i]), i);
	}
	da[N] = make_pair(0, -1);
	db[N] = make_pair(0, -1);
	sort(da, da + N + 1); reverse(da, da + N + 1);
	sort(db, db + N + 1); reverse(db, db + N + 1);
	double ans = DINF;
	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			if (da[i].second == db[j].second) continue;
			ans = min(ans, sum*2 - da[i].first - db[j].first);
		}
	}
	printf("%f\n", ans);
	return 0;
}