Submission #84614

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

#include <complex>
typedef complex<double> Point;
const double EPS = 1e-8;

// 入力ストリームから実数二つをとって Point へ
istream& operator >> ( istream &s, Point &a )
{
	double r, i;
	s >> r >> i;
	a = Point( r, i );
	return s;
}

// a == b
bool eq( const double a, const double b )
{
	return abs( a - b ) <= EPS;
}

// x 座標優先
// include : eq
struct CompX : public binary_function<Point,Point,bool>
{
	bool operator ()( const Point &a, const Point &b ) const
	{
		return eq( a.real(), b.real() ) ? a.imag() < b.imag() : a.real() < b.real();
	}
};

// 外積（クロス積）
double cross( const Point &a, const Point &b )
{
	return a.real() * b.imag() - a.imag() * b.real();
}

// 点 p と直線 ( q1, q2 ) の距離
// include : cross
double distancePL( const Point &p, const Point &q1, const Point &q2 )
{
	return abs( cross( q2 - q1, p - q1 ) ) / abs( ( q2 - q1 ) );
}

// 最小費用流 O( F |E| log |V| )
class MinimumCostFlow
{
private:
	struct Edge
	{
		int to, cap, rev;
		double cost;
		Edge( int t, int c, double d, int r ) : to( t ), cap( c ), cost( d ), rev( r ) {}
	};

	const int V;
	vector< vector<Edge> > G;

public:
	MinimumCostFlow( int v ) : V( v ), G( V ) {};

	void connect( int from, int to, int cap, double cost )
	{
		G[ from ].PB( Edge( to, cap, cost, G[ to ].size() ) );
		G[ to ].PB( Edge( from, 0, -cost, G[ from ].size() - 1 ) );
		return;
	}

	double solve( int s, int t, int f )
	{
		double res = 0;
		vector<double> h( V, 0 );
		vector<int> prevv( V ), preve( V );

		while ( 0 < f )
		{
			vector<double> distance( V, DBL_MAX / 4 );
			distance[s] = 0;

			priority_queue< pair<double,int>, vector< pair<double,int> >, greater< pair<double,int> > > que;
			que.push( make_pair( 0, s ) );
			
			while ( !que.empty() )
			{
				double d = que.top().first;
				int v = que.top().second;
				que.pop();

				if ( distance[v] < d )
				{
					continue;
				}

				for ( int i = 0; i < G[v].size(); ++i )
				{
					Edge &e = G[v][i];
					if ( 0 < e.cap && distance[v] + e.cost + h[v] - h[ e.to ] < distance[ e.to ] )
					{
						distance[ e.to ] = distance[v] + e.cost + h[v] - h[ e.to ];
						prevv[ e.to ] = v;
						preve[ e.to ] = i;
						que.push( make_pair( distance[ e.to ], e.to ) );
					}
				}
			}

			if ( distance[t] == DBL_MAX / 4 )
			{
				return -1;
			}

			for ( int i = 0; i < V; ++i )
			{
				h[i] += distance[i];
			}

			int d = f;
			for ( int v = t; v != s; v = prevv[v] )
			{
				d = min( d, G[ prevv[v] ][ preve[v] ].cap );
			}
			f -= d;
			res += d * h[t];
			for ( int v = t; v != s; v = prevv[v] )
			{
				Edge &e = G[ prevv[v] ][ preve[v] ];
				e.cap -= d;
				G[v][ e.rev ].cap += d;
			}
		}

		return res;
	}
};
// MinimumCostFlow( |V| )
// connect( from, to, cap, cost )
// solve( s, t, f )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	vector<Point> ps( n );
	FOR( p, ps )
	{
		cin >> p;
	}

	vector<Point> qs;
	transform( ALL( ps ), back_inserter( qs ), []( Point p ){ return Point( p.real() * -1, p.imag() ); } );

	MinimumCostFlow mcf( n * 2 + 2 );
	
	REP( i, 0, n )
	{
		REP( j, 0, n )
		{
			mcf.connect( i, n + j, 1, abs( ps[i] - qs[j] ) );
		}
	}
	REP( i, 0, n )
	{
		mcf.connect( n * 2, i, 1, 0 );
		mcf.connect( n + i, n * 2 + 1, 1, 0 );
	}

	cout << setprecision( 10 ) << fixed;
	cout << mcf.solve( n * 2, n * 2 + 1, n ) / 2 << endl;

	return 0;
}

Submission Info

Judge Result