SRM464 div1 medium

二部探索＋２SATらしい。

#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

class ColorfulDecoration 
{
	public:

		int n;
		int len;
		int dist[110][110];
		int G[110][110];

		int ABS(int n)
		{
			return (n<0)?-n:n;
		}

		bool check()
		{
			memset(G,0,sizeof(G));
			for(int i=0;i<2*n;i++)
				for(int j=0;j<2*n;j++)
					if(i%n!=j%n && dist[i][j]<len)
					{
						int ii=(i<n)?i+n:i-n;
						int jj=(j<n)?j+n:j-n;
						G[i][jj]=1;
					}

			for(int i=0;i<2*n;i++)
				G[i][i]=1;

			for(int k=0;k<2*n;k++)
				for(int i=0;i<2*n;i++)
					for(int j=0;j<2*n;j++)
						if(G[i][k]==1 && G[k][j]==1)
							G[i][j]=1;

			for(int i=0;i<n;i++)
				if(G[i][i+n] && G[i+n][i])
					return false;
			return true;
		}

		int getMaximum(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb) 
		{
			n=xa.size();
			for(int i=0;i<2*n;i++)
				for(int j=0;j<2*n;j++)
				{
					int x1=(i<n)?xa[i]:xb[i-n];
					int y1=(i<n)?ya[i]:yb[i-n];
					int x2=(j<n)?xa[j]:xb[j-n];
					int y2=(j<n)?ya[j]:yb[j-n];
					dist[i][j]=max(ABS(x1-x2),ABS(y1-y2));

					//printf("dist[%d][%d]=%d\n",i,j,dist[i][j]);
				}
			int ceil=1000000000,bottom=0;
			while(5<ceil-bottom)
			{
				len=(ceil+bottom)/2;
				if(check())
					bottom=len;
				else
					ceil=len;
			}
			for(len=ceil;bottom<=len;len--)
			{
				if(check())
					return len;
			}
			return 0;
		}
};