結果

問題 No.96 圏外です。
ユーザー Ysmr_RyYsmr_Ry
提出日時 2014-12-20 23:39:35
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,464 bytes
コンパイル時間 490 ms
コンパイル使用メモリ 53,216 KB
最終ジャッジ日時 2024-11-14 18:57:35
合計ジャッジ時間 1,957 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:181:48: error: ‘sqrt’ was not declared in this scope; did you mean ‘sqr’?
  181 |                         ans = std::max( ans, 2+sqrt((m[i][1]-m[i][0]).dot(m[i][1]-m[i][0])) );
      |                                                ^~~~
      |                                                sqr
main.cpp:187:56: error: ‘sqrt’ was not declared in this scope; did you mean ‘sqr’?
  187 |                                 ans = std::max( ans, 2+sqrt((m[i][chpts[k]]-m[i][chpts[j]]).dot(m[i][chpts[k]]-m[i][chpts[j]])) );
      |                                                        ^~~~
      |                                                        sqr
main.cpp:141:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  141 |         scanf( "%d", &N );
      |         ~~~~~^~~~~~~~~~~~
main.cpp:144:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  144 |                 scanf( "%d%d", X+i, Y+i );
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<cstdio>
#include<algorithm>
#include<map>
#include<numeric>
#include<vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define repd(i,a) for(int i=(a);i>=0;--i)
#define all(a) (a).begin(), (a).end()
#define itri(it,a,b) for(auto it=(a);it!=(b);++it)
#define itr(it,a) for(auto it=(a).begin();it!=(a).end();++it)

const int MAX_N = 120000;

struct UnionFind
{
	std::vector<int> par, rank;

	UnionFind( std::size_t sz )
	:	par(sz), rank(sz)
	{ std::iota( all(par), 0 ); }

	int find( int x )
	{ return x==par[x]?x:par[x]=find(par[x]); }

	void unite( int x, int y )
	{
		x = find(x);
		y = find(y);
		if( x == y )
			return;

		if( rank[x] < rank[y] )
			par[x] = y;
		else
		{
			par[y] = x;
			
			if( rank[x] == rank[y] )
				++rank[x];
		}

		return;
	}

	bool same( int x, int y )
	{ return find(x)==find(y); }
};

struct Pt
{
	double x, y;

	Pt()
	:	x(0), y(0)
	{}

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

	Pt operator+ ( const Pt &pt ) const
	{ return Pt( x+pt.x, y+pt.y ); }

	Pt operator- ( const Pt &pt ) const
	{ return Pt( x-pt.x, y-pt.y ); }

	Pt operator* ( double k ) const
	{ return Pt( k*x, k*y ); }

	bool operator< ( const Pt &pt ) const
	{
		if( x == pt.x )
			return y < pt.y;

		return x < pt.x;
	}

	double dot( const Pt &pt ) const
	{ return x*pt.x+y*pt.y; }

	double cross( const Pt &pt ) const
	{ return x*pt.y-y*pt.x; }
};

int N;

std::vector<int> convex_hull( const std::vector<Pt> &pts )
{
	if( pts.size() <= 2 )
	{
		std::vector<int> ret;

		if( pts.size() >= 1 )
			ret.push_back(0);
		else if( pts.size() == 2 )
			ret.push_back(1);
		
		return ret;
	}

	std::vector<std::pair<Pt, int> > sorted;
	rep( i, pts.size() )
		sorted.push_back( std::make_pair( pts[i], i ) );
	std::sort( all(sorted) );

	int k = 0;
	std::vector<int> ret( 2*pts.size() );

	rep( i, pts.size() )
	{
		while( k>1 && (pts[ret[k-1]]-pts[ret[k-2]]).cross(sorted[i].first-pts[ret[k-1]]) <= 0 )
			--k;

		ret[k++] = sorted[i].second;
	}

	int t = k;
	repd( i, pts.size()-2 )
	{
		while( k>t && (pts[ret[k-1]]-pts[ret[k-2]]).cross(sorted[i].first-pts[ret[k-1]]) <= 0 )
			--k;

		ret[k++] = sorted[i].second;
	}

	ret.resize( k-1 );

	return ret;
}

int sqr( int x )
{ return x*x; }

int X[MAX_N+1], Y[MAX_N+1];
std::map<int, int> pts[20015];
std::vector<Pt> m[MAX_N+1];

int main()
{
	scanf( "%d", &N );
	rep( i, N )
	{
		scanf( "%d%d", X+i, Y+i );
		pts[X[i]+=10001][Y[i]+=10001] = i;
	}

	UnionFind uf( N );
	rep( x, 20002 ) itr( it, pts[x] )
	{
		auto it2 = it;
		for( it2++; it2 != pts[x].end(); ++it2 )
		{
			if( it2->first-it->first > 10 )
				break;
			uf.unite( it->second, it2->second );
		}

		repi( x2, x+1, x+11 ) itri( it2, pts[x2].lower_bound( it->first-10 ), pts[x2].end() )
		{
			if( it2->first<it->first && sqr(x2-x)+sqr(it2->first-it->first) > 100 )
				continue;
			if( sqr(x2-x)+sqr(it2->first-it->first) > 100 )
				break;

			uf.unite( it->second, it2->second );
		}
	}

	rep( i, N )
		m[uf.find(i)].push_back( Pt( X[i], Y[i] ) );

	double ans = 1;
	rep( i, N ) if( !m[i].empty() )
	{
		auto msz = m[i].size();

		if( msz == 1 )
			ans = std::max( ans, 2.0 );
		else if( msz == 2 )
			ans = std::max( ans, 2+sqrt((m[i][1]-m[i][0]).dot(m[i][1]-m[i][0])) );
		else
		{
			auto chpts = convex_hull( m[i] );

			rep( j, chpts.size() ) rep( k, j )
				ans = std::max( ans, 2+sqrt((m[i][chpts[k]]-m[i][chpts[j]]).dot(m[i][chpts[k]]-m[i][chpts[j]])) );
		}
	}

	printf( "%.9f\n", ans );

	return 0;
}
0