[Codeforce Round #242]B. Megacity

題目網址: http://codeforces.com/contest/424/problem/B

題意: 以(0,0)為主城市及給定其人口數，以及n個城鎮(xi,yi)及其人口數，想以主城市為圓心建邊界圍住城鎮來增加人口數，問最小半徑的邊界圍住某些城鎮達成總人口數超過1百萬。



解法: 以離圓心的距離排序每個城鎮，累加至總人口數超過百萬。

TAG: greedy

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	using namespace std;
	#define EPS 1e-7
	const int dcmp( const double x )
	{
	if( x < -EPS ) return -1;
	return x > EPS;
	}
	struct Point {
	double x, y;
	int p;
	double d;
	Point( double _x = 0, double _y = 0, int _p = 0, double _d = 0 ):
	x(_x), y(_y), p(_p), d(_d) {}
	const bool operator<( const Point &op ) const { return ( dcmp(op.d-d) >= 0 ); }
	};
	int n, ppl;
	Point city[1005];
	int main( void )
	{
	int i;
	while( scanf( "%d%d", &n, &ppl ) == 2 ) {
	for( i = 0; i < n; ++i ) {
	scanf( "%lf%lf%d", &city[i].x, &city[i].y, &city[i].p );
	city[i].d = sqrt( city[i].x*city[i].x+city[i].y*city[i].y );
	}
	sort( city, city+n );
	for( i = 0; i < n && ppl < 1e6; ++i ) {
	ppl += city[i].p;
	}
	if( i == n && ppl < 1e6 ) puts("-1");
	else printf( "%.7lf\n", city[i-1].d );
	}
	return 0;
	}

view raw Megacity.cpp hosted with ❤ by GitHub